Pagini recente » Cod sursa (job #76278) | Cod sursa (job #286976) | Cod sursa (job #1177881) | Cod sursa (job #233653) | Cod sursa (job #284089)
Cod sursa(job #284089)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n, m, i, x, y, nrctc, nivel;
vector <int> v[100111], sol[100111];
stack <int> S;
int viz[100111], low[100111], niv[100111], in_stack[100111];
void citire(){
FILE *f = fopen("ctc.in", "r");
fscanf(f,"%d %d",&n,&m);
for(i=1; i<=m; i++){
fscanf(f,"%d %d",&x, &y);
v[x].push_back(y);
}
fclose(f);
}
void DFS(int nod){
nivel++;
low[nod] = niv[nod] = nivel;
vector <int>::iterator it;
S.push(nod); in_stack[nod] = 1;
for(it = v[nod].begin(); it != v[nod].end(); it++){
if( niv[*it] && !in_stack[*it] ) continue;
if( !niv[*it] ){
DFS(*it);
low[nod] = min(low[nod], low[*it]);
}
else
low[nod] = min(low[nod], low[*it]);
}
if( niv[nod] == low[nod] ){
nrctc++;
do{
x = S.top();
S.pop();
sol[nrctc].push_back(x);
in_stack[x] = 0;
} while( x != nod );
}
}
void solve(){
for(i=1; i<=n; i++)
if( !niv[i] )
DFS(i);
}
void afisare(){
vector <int>::iterator it;
FILE *g = fopen("ctc.out", "w");
fprintf(g,"%d\n",nrctc);
for(i = 1; i <= nrctc; i++){
for(it = sol[i].begin(); it != sol[i].end(); it++)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
fclose(g);
}
int main(){
citire();
solve();
afisare();
return 0;
}