Pagini recente » Cod sursa (job #730853) | Cod sursa (job #1174825) | Cod sursa (job #395066) | Cod sursa (job #279917) | Cod sursa (job #1583968)
#include <iostream>
#include <fstream>
#include <vector>
#define maxN 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m;
vector <int> v[maxN];
vector < vector <int> > ctc;
bool inQ[maxN];
int idx[maxN], lowlink[maxN], st[maxN];
void citire()
{
int x,y;
fin>>n>>m;
for (int i=1; i<=m; ++i)
{
fin>>x>>y;
v[x].push_back(y);
}
}
int minim(int a, int b)
{
if (a<b) return a;
return b;
}
void Tarjan(int x)
{
st[++st[0]]=x;
inQ[x]=true;
idx[x]=++idx[0];
lowlink[x]=idx[0];
for (int i=0; i<v[x].size(); ++i)
{
if (!idx[v[x][i]]) Tarjan(v[x][i]);
if (inQ[v[x][i]])
lowlink[x] = minim(lowlink[x], lowlink[v[x][i]]);
}
if (idx[x]==lowlink[x])
{
ctc.push_back(vector <int>());
while (st[st[0]]!=x)
{
ctc.back().push_back(st[st[0]]);
inQ[st[st[0]]]=false;
--st[0];
}
ctc.back().push_back(x);
inQ[x]=false;
--st[0];
}
}
int main()
{
citire();
for (int i=1; i<=n; ++i)
if (!idx[i]) Tarjan(i);
fout<<ctc.size()<<'\n';
for (int i=0; i<ctc.size(); ++i)
{
for (vector <int>::iterator it=ctc[i].begin(); it!=ctc[i].end(); ++it)
fout<<*it<<' ';
fout<<'\n';
}
return 0;
}