2010-1127

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这题的题意可以简化为,在一个图内，某两个点的所有路径的公共边。

首先对图进行dfs，找到其中的关键边（桥），在遍历得到的树中找到这两个点的路径，则这条路径中所包含的桥就是答案.需要注意的就是平行边的处理。


{{{
#!cpp
#include <cstdio>
#include <utility>
#include <cstring>
#include <vector>
using namespace std;


typedef pair<int,int> pii;

const int maxn=10100;
const int maxm=200100;
int prev[maxn];
int luangao[maxn];
int cnt;
int low[maxn];
int v[maxn];
vector<pii> e[maxn];

int gao(int f, int u , int t,int cnt){
    prev[u] = f; 
    luangao[u] = cnt;
    low[u] =luangao[u];
    v[u] =1;
    for(int i=0;i<e[u].size();++i)if(i!=t){
        int uu = e[u][i].first ;
//      if ( uu == f ) continue;
    //  if ( uu == u ) continue;
        if ( v[uu] == 1 ) {

            if ( luangao[uu] < low[u] ) low[u] =luangao[uu];

        }
        else if ( !v[uu] )  {

            gao(u,uu,e[u][i].second,cnt+1);
            if ( low[uu] < low[u] ) low[u] = low[uu];

        }
    }
    v[u]=2;
    return 0;
}
int n;

int gao2(int f, int u){
    if ( v[u] ) return 0 ;
    prev[u] = f; 
    v[u]=1;
    if ( u == n-1 ) return 1;
    for(int i=0;i<e[u].size();++i){
        if ( gao2(u,e[u][i].first) ) 
            return 1;
    }
    return 0;
}

int a[maxm],b[maxm];
int ok[maxm];
int main(){

    int m;
    while ( scanf("%d%d",&n,&m)!=EOF ) {
        for(int i=0;i<maxn;++i)e[i].clear();

        memset(ok,0,sizeof(ok));
        cnt=0;
        for(int i=0;i<m;++i){
            scanf("%d%d",a+i,b+i);
            e[a[i]].push_back(make_pair(b[i],e[b[i]].size()));
            e[b[i]].push_back(make_pair(a[i],e[a[i]].size()-1));
        }
        memset(prev,-1,sizeof(prev));
        memset(v,0,sizeof(v));
        memset(low,10,sizeof(low));
        memset(luangao,0,sizeof(luangao));
        gao(-1,0,-1,0);

        for(int i=0;i<m;++i){

            int u = a[i] , uu =b[i];
            if ( !v[u] || !v[uu] ) continue;
            if ( prev[u] == uu && luangao[uu] < low[u] || prev[uu] == u && luangao[u] < low[uu] ){
                ok[i] =1;
            }

        }

        int l[maxn];
        int tt =0;
/*memset(v,0,sizeof(v));
        memset(prev,-1,sizeof(prev));
        gao2(-1,0);*/
        for(int i=n-1;i!=-1;i=prev[i]){
            l[tt++]= i;
        }
        memset(prev,-1,sizeof(prev));
        for(int i=0;i<tt-1;++i){
            prev[l[i]] = l[i+1];
        }


        vector<int> ans;

        for(int i=0;i<m;++i)if ( ok[i] ) {
            if ( prev[a[i]] == b[i] || prev[b[i]] == a[i] ) 
                ans.push_back(i);
        }

        printf("%d\n" ,ans.size());
        for(int i =0;i<ans.size();++i){
            if ( i ) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");


    }

    return 0;
}


}}}

这题的题意可以简化为,在一个图内，某两个点的所有路径的公共边。

首先对图进行dfs，找到其中的关键边（桥），在遍历得到的树中找到这两个点的路径，则这条路径中所包含的桥就是答案.需要注意的就是平行边的处理。

#include <cstdio>
#include <utility>
#include <cstring>
#include <vector>
using namespace std;
typedef pair<int,int> pii;
const int maxn=10100;
const int maxm=200100;
int prev[maxn];
int luangao[maxn];
int cnt;
int low[maxn];
int v[maxn];
vector<pii> e[maxn];
int gao(int f, int u , int t,int cnt){
    prev[u] = f; 
    luangao[u] = cnt;
    low[u] =luangao[u];
    v[u] =1;
    for(int i=0;i<e[u].size();++i)if(i!=t){
        int uu = e[u][i].first ;
//      if ( uu == f ) continue;
    //  if ( uu == u ) continue;
        if ( v[uu] == 1 ) {
            if ( luangao[uu] < low[u] ) low[u] =luangao[uu];
        }
        else if ( !v[uu] )  {
            gao(u,uu,e[u][i].second,cnt+1);
            if ( low[uu] < low[u] ) low[u] = low[uu];
        }
    }
    v[u]=2;
    return 0;
}
int n;
int gao2(int f, int u){
    if ( v[u] ) return 0 ;
    prev[u] = f; 
    v[u]=1;
    if ( u == n-1 ) return 1;
    for(int i=0;i<e[u].size();++i){
        if ( gao2(u,e[u][i].first) ) 
            return 1;
    }
    return 0;
}
int a[maxm],b[maxm];
int ok[maxm];
int main(){
    int m;
    while ( scanf("%d%d",&n,&m)!=EOF ) {
        for(int i=0;i<maxn;++i)e[i].clear();
        memset(ok,0,sizeof(ok));
        cnt=0;
        for(int i=0;i<m;++i){
            scanf("%d%d",a+i,b+i);
            e[a[i]].push_back(make_pair(b[i],e[b[i]].size()));
            e[b[i]].push_back(make_pair(a[i],e[a[i]].size()-1));
        }
        memset(prev,-1,sizeof(prev));
        memset(v,0,sizeof(v));
        memset(low,10,sizeof(low));
        memset(luangao,0,sizeof(luangao));
        gao(-1,0,-1,0);
        for(int i=0;i<m;++i){
            int u = a[i] , uu =b[i];
            if ( !v[u] || !v[uu] ) continue;
            if ( prev[u] == uu && luangao[uu] < low[u] || prev[uu] == u && luangao[u] < low[uu] ){
                ok[i] =1;
            }
        }
        int l[maxn];
        int tt =0;
/*memset(v,0,sizeof(v));
        memset(prev,-1,sizeof(prev));
        gao2(-1,0);*/
        for(int i=n-1;i!=-1;i=prev[i]){
            l[tt++]= i;
        }
        memset(prev,-1,sizeof(prev));
        for(int i=0;i<tt-1;++i){
            prev[l[i]] = l[i+1];
        }
        vector<int> ans;
        for(int i=0;i<m;++i)if ( ok[i] ) {
            if ( prev[a[i]] == b[i] || prev[b[i]] == a[i] ) 
                ans.push_back(i);
        }
        printf("%d\n" ,ans.size());
        for(int i =0;i<ans.size();++i){
            if ( i ) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}