(UVA) 10731 - Test

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

SCC喔！

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

const int MAX_N = 30;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
bool visit[MAX_N];
bool used[MAX_N];
int stamp[MAX_N];
string scc[MAX_N];

inline int f(char c) {
    return c-'A'+1;
}

inline char ff(int x) {
    return x-1+'A';
}

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);
    }
    int len=scc[num].size();
    scc[num] += " ";
    scc[num][len] = ff(id);
}

int main (){
//    freopen("output.txt","w",stdout);
    int n;
    int cases=1;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        if (cases!=1) puts("");
        cases++;
        for (int x=0;MAX_N>x;x++) {
            edg[x].clear();
            rev_edg[x].clear();
            visit[x]=false;
            used[x]=false;
            scc[x]="";
        }
        for (int x=0;n>x;x++) {
            string i[6];
            for(int y=0;6>y;y++) cin>>i[y];
            int id=0;
            for (id=0;5>id;id++) {
                used[f(i[id][0])]=true;
                if (i[id]==i[5]) break;
            }
            for (int y=0;5>y;y++) {
                used[f(i[y][0])]=true;
                if (y==id) continue;
                edg[f(i[id][0])].push_back(f(i[y][0]));
                rev_edg[f(i[y][0])].push_back(f(i[id][0]));
            }
        }
        int cur_stamp=1;
        for (int x=1;MAX_N>x;x++) {
            if (visit[x]==false &&used[x]==true) dfs_for_stamp(x,cur_stamp);
        }
        for (int x=0;MAX_N>x;x++) {
            visit[x]=false;
        }
        int num=1;
        for (int x=cur_stamp-1;x>=1;x--) {
//            cout<<"x="<<x<<endl;
            if (visit[stamp[x]]==false) {
                dfs_for_scc(stamp[x],num++);
            }
        }
//        for (int x=1;num>x;x++) cout<<scc[x]<<endl;
//        cout<<"num="<<num<<endl;
        for (int x=1;num>x;x++) {
            string tmp[MAX_N];
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                tmp[y]=" ";
                tmp[y][0]=scc[x][y];
            }
            sort(tmp,tmp+len);
            scc[x]="";
            for (int y=0;len>y;y++) {
                scc[x] += tmp[y];
            }
        }
        sort(scc+1,scc+num);
        for (int x=1;num>x;x++) {
            int len=scc[x].size();
            for (int y=0;len>y;y++) {
                if (y!=0) printf(" ");
                char t=scc[x][y];
                printf("%c",t);
            }
            puts("");
        }
    }
}