Pagini recente » Cod sursa (job #1828541) | Cod sursa (job #1625657) | Cod sursa (job #2693674) | Cod sursa (job #395477) | Cod sursa (job #2166429)
#include <bits/stdc++.h>
using namespace std;
int pre[100005],lowlink[100005],idx,n,nr=0;
vector<int> v[100005],comp;
vector< vector<int> > ctc;
stack<int> stiva;
void dfs(int i)
{
pre[i]=idx;
lowlink[i]=idx;
idx++;
stiva.push(i);
for (size_t k=0;k<v[i].size();k++)
{
int j=v[i][k];
if (pre[j]==-1)
dfs(j);
lowlink[i]=min(lowlink[i],lowlink[j]);
}
if (lowlink[i]==pre[i])
{
while (true)
{
int x=stiva.top();
stiva.pop();
pre[x]=nr;
lowlink[x]=n;
comp.emplace_back(x);
if (x==i)
break;
}
nr++;
ctc.emplace_back(comp);
comp.clear();
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int m,i,y,x,j;
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
v[x].emplace_back(y);
}
for (i=1;i<=n;i++)
pre[i]=-1;
for (i=1;i<=n;i++)
{
if (pre[i]==-1)
dfs(i);
}
g<<nr<<endl;
for (i=0;i<nr;i++)
{
for (j=ctc[i].size()-1;j>=0;j--)
g<<ctc[i][j]<<" ";
g<<endl;
}
return 0;
}