Pagini recente » Cod sursa (job #2083604) | Cod sursa (job #1174501) | Cod sursa (job #288849) | Cod sursa (job #1659117) | Cod sursa (job #2216142)
#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, numSCC, vf;
bool onStack[MAX_N+1];
inline int minim(int x, int y) {
if(x <= y) return x;
return y;
}
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 dfsTarjan(int node) {
visitedTime[node] = lowTime[node] = ++time;
st[++vf] = node;
onStack[node] = true;
for(auto i : g[node]) {
if(!visitedTime[i]) {
dfsTarjan(i);
lowTime[node] = minim(lowTime[node],lowTime[i]);
} else if(onStack[i])
lowTime[node] = minim(lowTime[node],lowTime[i]);
}
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])
dfsTarjan(i);
}
void printSCC() {
int i, k, j;
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;
}