UVA 247 - Calling Circles

247 - Calling Circles

有一家電信公司記錄了所有人之間打電話的紀錄，他們想找出所有的通話圈圈(calling circles)

舉例來說，如果A打給B，B打給C，C又打給A，ABC之間就可以跟任何一個人互相溝通，他們就形成一個calling circle。但假如D可以打給A，但A不能打給D，D跟A就不算calling circle。

輸入

每筆測資先給你總共的人數n，和通話紀錄m筆

接下來m行會有兩個人名(25字元以內)，代表前面的人打給後面的人(單向)。

輸出

每筆測資先輸出一行"Calling circles for data set x:"(x代表第幾筆)

接下來每行輸出一個calling circle中的所有人名，之間以逗號和空白隔開，順序都可以

Sample Input

5 6
Ben Alexander
Alexander Dolly
Dolly Ben
Dolly Benedict
Benedict Dolly
Alexander Aaron
14 34
John Aaron
Aaron Benedict
Betsy John
Betsy Ringo
Ringo Dolly
Benedict Paul
John Betsy
John Aaron
Benedict George
Dolly Ringo
Paul Martha
George Ben
Alexander George
Betsy Ringo
Alexander Stephen
Martha Stephen
Benedict Alexander
Stephen Paul
Betsy Ringo
Quincy Martha
Ben Patrick
Betsy Ringo
Patrick Stephen
Paul Alexander
Patrick Ben
Stephen Quincy
Ringo Betsy
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Betsy Benedict
Quincy Martha
0 0

Sample Output

Calling circles for data set 1:
Ben, Alexander, Dolly, Benedict
Aaron

Calling circles for data set 2:
John, Betsy, Ringo, Dolly
Aaron
Benedict
Paul, George, Martha, Ben, Alexander, Stephen, Quincy, Patrick

這題就是找出所有強連接元件(strong connected vertex)。

做法是以dfs搜索每個點並編號(存在dfn陣列裡)，同時把每個搜過的點丟到一個stack中，假如遇到編號比自己小的(之前搜過的點)，就代表有環產生，此時會把這個值(能到達最前面的點)紀錄在low陣列裡，每做完一次dfs都要檢查下一個的low如果比自己小，自己的low也要更新。

簡單的說，dfn是紀錄順序，而low是每個點可以到達最前面的點。

假如一個點x做完每條dfs而dfn仍然等於low(一開始是設為相等)，代表兩種情況：他不屬於一個環，或他是一個環中最前面的點，而這兩種情況其實都是強連接元件(只是第一個情況只有自己)。

這時候就把存在stack中的點一個一個丟出來，直到丟出x，這些點就是一個強連接元件，也就是一個calling circle。

注意題目的圖可能不連通，所以要dfs多次。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <stack>

using namespace std;

map<string,int> trans;
char str[110][50];
int low[110],dfn[110],t,countt;
vector<int> v[110],ans[110];
stack<int> s;
bool used[110];

bool exist(string key){
    return trans.find(key) != trans.end();
}

void dfs(int cur){
    int next,children=0,i,x;
    low[cur]=t;
    dfn[cur]=t;
    t++;
    s.push(cur);
    for(i=0;i<v[cur].size();i++){
        next=v[cur][i];
        if(dfn[next]==0){
            children++;
            dfs(v[cur][i]);
            if(low[cur]>low[next])low[cur]=low[next];
        }
        else if(!used[next]){
            if(dfn[next]<low[cur]){
                low[cur]=dfn[next];
            }
        }
    }
    if(low[cur]==dfn[cur]){
        for(;;){
            x=s.top(); s.pop();
            used[x]=true;
            ans[countt].push_back(x);
            if(x==cur){
                countt++;
                break;
            }
        }
    }
    return;
}

int main()
{
    int n,i,j,cur,m,a,b,c=1,num;
    char s1[50],s2[50];
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0 && m==0)break;
        countt=0;
        t=1;
        memset(low,0,sizeof(low));
        memset(dfn,0,sizeof(dfn));
        memset(used,false,sizeof(used));
        if(c!=1)printf("\n");
        printf("Calling circles for data set %d:\n",c++);
        for(i=0;i<m;i++){
            scanf("%s %s",s1,s2);
            if(!exist(s1)){
                trans[s1]=countt;
                sscanf(s1,"%s",str[countt]);
                countt++;
            }
            if(!exist(s2)){
                trans[s2]=countt;
                sscanf(s2,"%s",str[countt]);
                countt++;
            }
            a=trans[s1]; b=trans[s2];
            v[a].push_back(b);
        }
        num=countt;
        countt=0;
        for(i=0;i<num;i++){
            if(!used[i]){
                dfs(i);
            }
        }
        for(i=0;i<countt;i++){
            for(j=0;j<ans[i].size();j++){
                if(j!=0)printf(", ");
                printf("%s",str[ans[i][j]]);
            }
            printf("\n");
        }
        trans.clear();
        for(i=0;i<n;i++){
            v[i].clear();
            ans[i].clear();
        }
    }
    return 0;
}