Pagini recente » Cod sursa (job #2453479) | Cod sursa (job #2679044) | Cod sursa (job #2319967) | Cod sursa (job #2965963) | Cod sursa (job #712501)
Cod sursa(job #712501)
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
FILE *f,*g;
stack <int> S;
int x,y,n,m,i,j,index=1,bf[100100];
vector <int> ax;
vector < vector <int> > sol;
vector < int > a[100100];
struct cp{int ind,mn; } v[100100];
void tarjan(int x) {
int i;
v[x].ind=v[x].mn=index;
S.push(x);
index++;
bf[x]=1;
for (i=0;i<a[x].size();i++)
if (!v[a[x][i]].ind) {
tarjan(a[x][i]);
v[x].mn=min(v[x].mn,v[a[x][i]].mn);
}
else
if (bf[a[x][i]]==1) {
v[x].mn=min(v[x].mn,v[a[x][i]].mn);
}
if (v[x].ind==v[x].mn) {
ax.clear();
int cn;
do {
ax.push_back(cn=S.top());
bf[cn]=0;
S.pop();
}
while (cn!=x);
sol.push_back(ax);
}
}
int main() {
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++) {
fscanf(f,"%d%d",&x,&y);
a[x].push_back(y);
}
for (i=1;i<=n;i++)
if (v[i].ind==0)
tarjan(i);
fprintf(g,"%d\n",sol.size());
for (i=0;i<sol.size();i++,fprintf(g,"\n"))
for (j=0;j<sol[i].size();j++)
fprintf(g,"%d ",sol[i][j]);
fclose(g);
return 0;
}