Pagini recente » Cod sursa (job #1469023) | Cod sursa (job #433393) | Cod sursa (job #3168592) | Cod sursa (job #3142065) | Cod sursa (job #3215665)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,indecs,instack[100001],idx[100001],lowlink[100001],ctc;
vector<int> G[100001],cc[100001];
stack<int> S;
void tarjan(int nod, int& ctc)
{
idx[nod]=lowlink[nod]=indecs;
indecs++;
S.push(nod);
instack[nod]=1;
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
{
if(idx[*it]==-1)
{
tarjan(*it,ctc);
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}
else
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}
if(idx[nod]==lowlink[nod])
{
while(S.top()!=nod)
{
instack[S.top()]=0;
cc[ctc].push_back(S.top());
S.pop();
}
instack[nod]=0;
cc[ctc].push_back(nod);
ctc++;
S.pop();
}
}
int main()
{
fin >> n >> m;
for(int i=1;i<=m;i++)
{
int x,y;
fin >> x >> y;
G[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
idx[i]=-1;
lowlink[i]=0;
}
indecs=1;
ctc=1;
for(int i=1;i<=n;i++)
{
if(idx[i]==-1)
{
tarjan(i,ctc);
}
}
fout << ctc-1 << "\n";
for(int i=1;i<ctc;i++)
{
for(vector<int>::iterator it=cc[i].begin();it!=cc[i].end();++it)
fout << *it << " ";
fout << "\n";
}
return 0;
}