Pagini recente » Cod sursa (job #2122648) | Cod sursa (job #1626155) | Cod sursa (job #923627) | Cod sursa (job #159168) | Cod sursa (job #2334028)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
vector<int> v[NMAX];
vector<int> sol[NMAX];
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
int n,m,x,y,viz[NMAX],st[NMAX],nr,nrctc,ll[NMAX],idx[NMAX],index;
void df(int k) {
int i,u,x;
viz[k]=1;
idx[k]=ll[k]=++index;
st[++nr]=k;
for (i=0;i<v[k].size();++i) {
u=v[k][i];
if (!idx[u]) {
df(u);
ll[k]=min(ll[u],ll[k]);
}
else if (viz[u])
ll[k]=min(ll[u],ll[k]);
}
if (ll[k]==idx[k]) {
++nrctc;
do {
x=st[nr--];
viz[x]=0;
sol[nrctc].push_back(x);
}while (x!=k);
}
}
int main() {
int i,j;
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;++i) {
fscanf(f,"%d%d",&x,&y);
v[x].push_back(y);
}
for (i=1;i<=n;++i)
if (!idx[i]) df(i);
fprintf(g,"%d\n",nrctc);
for (i=1;i<=nrctc;++i) {
for (j=0;j<sol[i].size();j++)
fprintf(g,"%d ",sol[i][j]);
fprintf(g,"\n");
}
return 0;
}