Pagini recente » Cod sursa (job #2794519) | Cod sursa (job #1843053) | Cod sursa (job #1554673) | Cod sursa (job #1480477) | Cod sursa (job #1132122)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define nr 100001
vector <int> v[nr],comp[nr];
stack <int> S;
bool in_stack[nr];
int index[nr],low_link[nr],poz=0,ix=0;
void tarjan(int x)
{
index[x]=ix;
low_link[x]=ix;
in_stack[x]=1;
ix++;
S.push(x);
for(int l=0;l<v[x].size();++l)
if(index[v[x][l]]==-1)
{
tarjan(v[x][l]);
low_link[x]=min(low_link[x],low_link[v[x][l]]);
}
else
if(in_stack[v[x][l]]==1)
low_link[x]=min(low_link[x],index[v[x][l]]);
if(low_link[x]==index[x])
{
int w;
do
{
w=S.top();
S.pop();
in_stack[w]=0;
comp[poz].push_back(w);
}
while(w!=x);
poz++;
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,xx,y;
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>xx>>y;
v[xx].push_back(y);
}
for(i=1;i<=n;++i)
{
index[i]=-1;
in_stack[i]=0;
}
for(i=1;i<=n;++i)
if(index[i]==-1)
tarjan(i);
g<<poz<<'\n';
for(i=0;i<poz;++i)
{
for(int j=0;j<comp[i].size();++j)
g<<comp[i][j]<<" ";
g<<'\n';
}
f.close();
g.close();
return 0;
}