Pagini recente » Cod sursa (job #1594620) | Cod sursa (job #1517559) | Cod sursa (job #1580820) | Cod sursa (job #1032654) | Cod sursa (job #3256519)
#include<bits/stdc++.h>
#define inf 1000005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, ss, ps[100005], d[100005], nrctc;
vector<int> l[100005], sol[100005];
stack<int> stiva;
int tarjan(int u, int depth)
{
d[u]=depth;
ps[u]=1;
stiva.push(u);
for(int i=0; i<l[u].size(); i++)
{
if(d[l[u][i]]==inf)
d[u]=min(d[u], tarjan(l[u][i], depth+1));
else if(ps[l[u][i]]==1)
d[u]=min(d[u], d[l[u][i]]);
}
if(d[u]==depth)
{
int v;
nrctc++;
do{
v=stiva.top();
ps[v]=0;
stiva.pop();
sol[nrctc].push_back(v);
}while(v!=u);
}
return d[u];
}
int main()
{
fin>>n>>m;
while(m)
{
int x,y;
fin>>x>>y;
l[x].push_back(y);
m--;
}
for(int i=1; i<=n; i++)
d[i]=inf;
for(int i=1; i<=n; i++)
if(d[i]==inf)
tarjan(i, i);
fout<<nrctc<<"\n";
for(int i=1; i<=nrctc; i++)
{
//cout<<i<<": ";
for(int j=0; j<sol[i].size(); j++)
fout<<sol[i][j]<<" ";
fout<<"\n";
}
}