(UVA) 247 - Calling Circles

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=183

SCC進化版XD

處理字串那裏比較難啦XD

#include <iostream>
#include <stdio.h>
#include <vector>
#include <map>
#include <cstring>
using namespace std;

const int MAX_N = 30;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
vector<int> scc[MAX_N];
bool visit[MAX_N];
int stamp[MAX_N];
map<string,int> mp;
string rev_mp[MAX_N];

void dfs_for_stamp(int id,int &cur_stamp) {
    visit[id]=true;
    for (auto i=rev_edg[id].begin();i!=rev_edg[id].end();i++) {
        int tmp=*i;
        if(visit[tmp]==false) dfs_for_stamp(tmp,cur_stamp);
    }
    stamp[cur_stamp++]=id;
}

void dfs_for_scc(int id,int num) {
    visit[id]=true;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==false) dfs_for_scc(tmp,num);
    }
    scc[num].push_back(id);
}

int main () {
    int n,m;
    int cases=1;
    while (cin >> n >> m) {
        if (!n && !m) break;
        mp.clear();
        for (int x=0;n>=x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            scc[x].clear();
            visit[x]=false;
        }
        int id=1;
        for (int x=0;m>x;x++) {
            string i,j;
            cin >> i >>j;
            if(mp.find(i) == mp.end()) {
                mp[i]=id;
                rev_mp[id++]=i;
            }
            if (mp.find(j) == mp.end()) {
                mp[j]=id;
                rev_mp[id++]=j;
            }
            edg[mp[i]].push_back(mp[j]);
            rev_edg[mp[j]].push_back(mp[i]);
        }
        int cur_stamp=1;
        for (int x=1;n>=x;x++) {
            if (visit[x]==false) {
                dfs_for_stamp(x,cur_stamp);
            }
        }
        for(int x=1;n>=x;x++) {
            visit[x]=false;
        }
        int num=1;
        for (int x=n;x>=1;x--) {
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],num++);
            }
        }
        if (cases!=1) cout<<endl;
        cout<<"Calling circles for data set "<<cases++<<":\n";
        for(int x=1;num>x;x++) {
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                if (y!=0) cout<<", ";
                cout<<rev_mp[scc[x][y]];
            }
            cout<<endl;
        }
    }
}