强连通分量 tarjan

poj 3114， tarjan算法不是很熟， 先贴代码;View Code

Source CodeProblem: 3114  User: hehexiaobai Memory: 2136K  Time: 282MS Language: C++  Result: Accepted Source Code #include<iostream>#include<cstdio>#include<cstring>#include<stack>using namespace std;const int MAXCITY = 505;const int inf = (1 << 28);inline int min(int a, int b){ return a > b ? b : a; }inline int max(int a, int b){ return a > b ? a: b ; }int mp[MAXCITY][MAXCITY];int dfn[MAXCITY];int low[MAXCITY];int _stack[MAXCITY], sp;bool instack[MAXCITY];int father[MAXCITY];int newGraph[MAXCITY][MAXCITY];int d[MAXCITY];bool visit[MAXCITY];int nscc;int N, E, K;int time;void tarjan(int u){    time ++;    dfn[u] = low[u] = time;    _stack[sp] = u;    sp ++;    instack[u] = true;    for(int i = 1; i <= N; i ++)        if(mp[u][i] != 0)        {            if(dfn[i] == 0)            {                tarjan(i);                low[u] = min(low[u], low[i]);            }            else if(instack[i] == true )                low[u] = min(low[u], dfn[i]);        }    if(dfn[u] == low[u])    {        nscc++;        do        {            sp--;            father[_stack[sp]] = nscc;            instack[_stack[sp]] = false;        }while( _stack[sp] != u);    }}void constructGraph(){    int i , j;    //cout << "nscc   " << nscc << endl;    for(i = 1; i <= nscc; i ++)        for(j = 1; j <= nscc; j ++)            newGraph[i][j] = inf;        for(i = 1; i <= N; i ++)        for(j = 1; j <= N; j ++)        {            if(father[i] == father[j])newGraph[father[i]][father[j]] = 0;            else            if(mp[i][j] != 0 && mp[i][j] < newGraph[father[i]][father[j]])                 newGraph[father[i]][father[j]] =  mp[i][j];        }        /*for(i = 1; i <= nscc; i ++, cout << endl)            for(j = 1; j <= nscc; j ++)                cout << newGraph[i][j] << "  ";        cout << endl;*/}void dijstra(int start){    memset(visit, 0, sizeof visit);        for(int i = 1; i <= nscc; i ++)        d[i] = inf;    d[start] = 0;  // visit[start] = 1 //别再加了。。。 调了很久    int i, j;    for(i =1 ; i <= nscc; i ++)    {        int min = inf, index;        for(j = 1; j <= nscc; j ++)        {            if(visit[j] == false && d[j] < min)            {                min = d[j];                index = j;            }        }                    if(min == inf)break;        visit[index] = 1;                    for(j = 1; j <= nscc; j ++)                if(d[j] > d[index] + newGraph[index][j])                    d[j] = d[index] + newGraph[index][j];    }}int main(){    while(scanf("%d %d",&N, &E) != EOF)    {        if(N == 0) break;        int s, t, v;        memset(father, 0, sizeof (father));        memset(mp, 0, sizeof (mp));        memset(dfn,0,sizeof (dfn ));        memset(low, 0, sizeof (low));        memset(_stack, 0, sizeof (_stack));        memset(instack, 0, sizeof (instack));        for(int i = 0; i < E; i ++)        {            scanf("%d %d %d",&s, &t, &v);            mp[s][t] = v;        }        sp = 0;        time = 0;        nscc = 0;        for(int i = 1 ; i <= N; i ++)            if(dfn[i] == 0)                tarjan(i);        //for(int i = 1; i <= N; i ++)            //printf("%d ",father[i]);        //printf("n");            constructGraph();            int K;        int ss, tt;        scanf("%d",&K);        for(int i = 1 ; i <= K ; i ++)        {            scanf("%d %d",&ss, &tt);            ss = father[ss];            tt = father[tt];            dijstra(ss);            if(d[tt] ==inf)printf("Nao e possivel entregar a cartan");            else printf("%dn",d[tt]);        }        printf("n");    }    return 0;}

-------------------------------------------------------------------------------------------------------------------------------poj 3352 边联通分量边联通分量就是去掉任意一条边后，图 依然是联通的。题要求添加最少的边使变成边联通的。先求出所有的桥，求桥的时候进行搜索会形成一棵树，把所有的桥去掉再对树进行搜索就会形成一个个的边联通分支，缩点后会形成一棵新的树，统计一下度数为1的节点的个数，如果个数为ans ， 结果就为(ans + 1)/2，即度数为1 的节点两两合并。3352代码

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAX = 1005;inline int min(int a, int b) { return a > b ? b : a;  }int low[MAX], dfn[MAX];int mp[MAX][MAX];int parent[MAX];int belong[MAX], nedge = 0;   //belong[i] 的值代表 节点i 属于 的边联通分量的序号   nedge代表边联通分量的个数int n, r, time = 0;int degree[MAX];void tarjan(int u){    time++;    dfn[u] = low[u] = time;    for(int i =1; i <= n; i ++)        if(mp[u][i] == 1)        {                if(low[i] == 0)    //i  is not visited                {                        parent[i] = u;                        tarjan(i);                        low[u] = min(low[u], low[i]);                         if(dfn[u] < low[i])//(u, i)是桥， 值为2的边标记为桥                            mp[u][i] ++;                }                else                {                        if(parent[u] != i)                                low[u] = min(low[u], dfn[i]);                }        }}//去掉是桥的那些边， 进行dfs， 找到所有的边联通分量void  dfs(int u)   //形成一棵新的树{    belong[u] = nedge;    for(int i = 1; i <= n; i ++)        if(  parent[i] == u && mp[u][i] ==1 && belong[i] == 0)        {            dfs(i);        }}int main(){    memset(low, 0, sizeof (low));    memset(dfn, 0, sizeof (dfn));    memset(mp, 0, sizeof(mp));    memset(belong, 0, sizeof (belong));    memset(degree, 0, sizeof (degree));    scanf("%d %d",&n, &r);    int s, t;    for(int i = 1 ; i <= r; i ++)    {        scanf("%d %d",&s, &t);        mp[s][t] = 1;        mp[t][s] = 1;    }    tarjan(1);    //for(int i =1 ; i <= n; i ++)    //{        //cout << dfn[i] <<" "<< low[i]<<"  "<< parent[i] << endl;    //}    //for(int i = 1; i <= n; i ++,cout << endl)        //for(int j = 1; j <= n; j ++)    //        cout << mp[i][j] <<' ';//    cout << endl;    nedge = 0;    for(int i =  1;  i <= n; i ++)        if(belong[i] == 0)  //如果i节点所属于哪个边联通分量还没确定，则开始搜索        {            nedge ++;            dfs(i);        }    //for(int j = 1; j <= n; j++)        //    cout << belong[j] << ' ';//    cout << endl;    //统计入度为1的点    for(int i =  1; i <= n; i ++)        for(int j = 1; j <= n; j ++)            {            if(mp[i][j] == 2)            {                degree[belong[i]]++;                degree[belong[j]]++;            }        }    int ans = 0;    for(int i = 1 ;i <= nedge; i ++)        if(degree[i] == 1)            ans ++;    printf("%dn", (ans + 1)/2);    cin >> ans;    return 0;}//4 3 1 2 2 3 3 4

原文链接: https://www.cnblogs.com/blog-of-tb/archive/2011/03/21/1990813.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍