Pagini recente » Cod sursa (job #1031374) | Cod sursa (job #1112814) | Cod sursa (job #1377892) | Cod sursa (job #1983313) | Cod sursa (job #633741)
Cod sursa(job #633741)
#include <stdio.h>
#include <vector>
using namespace std;
#define maxn 100005
vector <int> graf[maxn],graft[maxn],tc[maxn];//tc[i] tine toate nodurile din componenta conexa a i-a
int stiva[maxn],vf=0,conex;
bool viz[maxn];
void dfs1(int start){//parcurg graful direct si bag in stiva
int i;
viz[start]=1;
for(i=0;i<graf[start].size();i++){
if(!viz[graf[start][i]]){
dfs1(graf[start][i]);
}
}
stiva[vf]=start;
vf++;
}
void dfs2(int start){//parcurg graful transpus
int i;
viz[start]=0;
tc[conex].push_back(start);
for(i=0;i<graft[start].size();i++){
if(viz[graft[start][i]]){
dfs2(graft[start][i]);
}
}
}
int main(){
int n,m;
FILE *fin=fopen("ctc.in","r");
FILE *fout=fopen("ctc.out","w");
int i,j;
int a,b;
fscanf(fin,"%d%d",&n,&m);
for(i=0;i<m;i++){
fscanf(fin,"%d%d",&a,&b);
graf[a].push_back(b);
graft[b].push_back(a);
}
//nodurile incep de la 1
for(i=1;i<=n;i++)
if(!viz[i]){
dfs1(i);
}
conex=0;
for(i=n-1;i>=0;i--){
if(viz[stiva[i]]){
dfs2(stiva[i]);
conex++;
}
}
//afisez
fprintf(fout,"%d\n",conex);
for(i=0;i<conex;i++){//a i-a componenta conexa
for(j=0;j<tc[i].size();j++)
fprintf(fout,"%d ",tc[i][j]);
fprintf(fout,"\n");
}
return 0;
}