Pagini recente » Cod sursa (job #1631566) | Cod sursa (job #405743) | Cod sursa (job #2138819) | Cod sursa (job #1053145) | Cod sursa (job #2151025)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N + 1], scc[MAX_N + 1];
int visitedTime[MAX_N + 1], lowTime[MAX_N + 1], st[MAX_N + 1], n, m, time, vf, numSCC;
bool onStack[MAX_N + 1];
inline int minim(int a, int b) {
if(a <= b) return a;
return b;
}
void readGraph() {
int i, x, y;
FILE *fin = fopen("ctc.in","r");
fscanf(fin,"%d%d",&n,&m);
for(i = 0; i < m; i++) {
fscanf(fin,"%d%d",&x,&y);
g[x].push_back(y);
}
fclose(fin);
}
void DFS(int node) {
vector<int>::iterator it;
st[++vf] = node;
onStack[node] = true;
visitedTime[node] = lowTime[node] = ++time;
for(it = g[node].begin(); it != g[node].end(); it++) {
if(!visitedTime[*it]) {
DFS(*it);
lowTime[node] = minim(lowTime[node],lowTime[*it]);
} else if(onStack[*it])
lowTime[node] = minim(lowTime[node],lowTime[*it]);
}
if(visitedTime[node] == lowTime[node]) {
do {
scc[numSCC].push_back(st[vf]);
onStack[st[vf]] = false;
vf--;
}while(st[vf + 1] != node);
numSCC++;
}
}
void DFS_master() {
for(int i = 1; i <= n; i++)
if(!visitedTime[i])
DFS(i);
}
void printSCC() {
int i, j, k;
FILE *fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",numSCC);
for(i = 0; i < numSCC; i++) {
k = scc[i].size();
for(j = 0; j < k; j++)
fprintf(fout,"%d ",scc[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
DFS_master();
printSCC();
return 0;
}