Why ???!!!!!!! i cant understand ...
I'll be Grateful for any help
Code: Select all
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
vector<int> Graph[2][26]; // 0 original - 1Transpose
int f[26],Time;
int mark[26];
int Tsort[26],TsortC=0;
int SCC[26];
char in[10];
void DFS(int ca,int v,int GT,int comp, bool TF){
mark[v]=ca;
Time++;
FOR(i,Graph[GT][v].size() ){
int n=Graph[GT][v][i];
if(mark[n]!=ca )DFS(ca,n,GT,comp,TF);
}
if(!TF) SCC[v]=comp;
if(TF) f[v]=++Time, Tsort[TsortC++]=v;
}
int main(){
int n,ca=0;
char t;
//freopen("in.txt","r",stdin);
while(scanf("%d",&n)>0 && n){
if(ca++)putchar('\n'); //Making the Graph and its Transpose ...
FOR(i,n){
scanf(" %c %c %c %c %c %c",&in[0],&in[1],&in[2],&in[3],&in[4],&t);
FOR(k,5){
if( t==in[k] )continue;
Graph[0][ t-'A' ].push_back( in[k]-'A' );
Graph[1][ in[k]-'A' ].push_back( t-'A' );
}
}
Time =0; // T-Sorint the Graph
FOR(v,26)
if(mark[v]!=ca && Graph[0][v].size()!=0 )
DFS(ca,v,0,0,true);
ca++;
reverse(Tsort,Tsort+TsortC); // finiding SCC by a DFS on Graph Transpose ...
int comp=10;
FOR(i,TsortC)
if( mark[ Tsort[i] ]!=ca )
DFS(ca,Tsort[i],1,++comp,false);
FOR(i,26){
if( SCC[i]>0 ){
printf("%c",i+'A');
int cmp=SCC[i];
FOR(k,26)
if(cmp==SCC[k] && k!=i )
SCC[k]=0,printf(" %c",'A'+k);
putchar('\n');
}
}
FOR(i,26) Graph[0][i].clear(),Graph[0][i].clear(),SCC[i]=0;
TsortC=0;
}
return 0;
}