Pagini recente » Cod sursa (job #1077535) | Cod sursa (job #3175682) | Cod sursa (job #251354) | Cod sursa (job #1588609) | Cod sursa (job #799877)
Cod sursa(job #799877)
#include<stdio.h>
#define dim 100010
#include<vector>
#include<algorithm>
using namespace std;
int viz[dim],low[dim],next,i,j,n,m,nr,a,b,stiva[dim],ctc;
vector <int> P[dim];
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
struct nod{
int nr;
nod *adr;
}*p,*L[dim];
void read(){
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
p=new nod;
p->nr=b;
p->adr=L[a];
L[a]=p;
}
}
int min(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int x){
next++;
viz[x]=next;
low[x]=next;
stiva[++stiva[0]]=x;
nod *c;
for(c=L[x];c!=0;c=c->adr){
if(!viz[c->nr]){
dfs(c->nr);
low[x]=min(low[x],low[c->nr]);
}
else{
if(viz[c->nr]>0)
low[x]=min(low[x],low[c->nr]);
}
}
if(viz[x]==low[x]){
int v;
ctc++;
do {
v = stiva[stiva[0]--];
viz[v] = - viz[v];
P[ctc].push_back(v);
} while (v!=x);
}
}
int main(){
read();
for(i=1;i<=n;i++){
if(!viz[i]){
dfs(i);
}
}
fprintf(g,"%d\n",ctc);
for (i=1;i<=ctc;i++) {
for (j=0;j<P[i].size();j++)
fprintf(g,"%d ",P[i][j]);
fprintf(g,"\n");
}
return 0;
}