Pagini recente » Cod sursa (job #570626) | Cod sursa (job #232051) | Cod sursa (job #1949835) | Cod sursa (job #658921) | Cod sursa (job #2371427)
#include<cstdio>
#include<vector>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N+1], gt[MAX_N+1], ctc[MAX_N+1];
int f[MAX_N+1], n, m, k, nrctc;
bool used[MAX_N+1];
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);
gt[y].push_back(x);
//printf("%d %d\n",x,y);
}
fclose(fin);
}
void DFS(int nod) {
used[nod] = true;
for(auto i : g[nod])
if(!used[i])
DFS(i);
f[k++] = nod;
}
void DFS_Master(int n) {
for(int i = 1; i <= n; i++)
if(!used[i])
DFS(i);
}
void DFSreverseGraph(int nod) {
used[nod] = true;
ctc[nrctc].push_back(nod);
for(auto i : gt[nod])
if(!used[i])
DFSreverseGraph(i);
}
void Kosaraju() {
int i;
DFS_Master(n);
nrctc = 0;
for(i = 1; i <= n; i++)
used[i] = false;
for(i = k - 1; i >= 0; i--)
if(!used[f[i]]) {
DFSreverseGraph(f[i]);
nrctc++;
}
}
void printCTC() {
int j;
FILE* fout = fopen("ctc.out","w");
fprintf(fout,"%d\n",nrctc);
for(j = 0; j < nrctc; j++) {
for(auto i : ctc[j])
fprintf(fout,"%d ",i);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
Kosaraju();
printCTC();
return 0;
}