Pagini recente » Cod sursa (job #288654) | Cod sursa (job #718379) | Cod sursa (job #1928597) | Cod sursa (job #1697099) | Cod sursa (job #1376234)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,j,k,a,b,timp;
struct coce{int viz,in,out;} nod[100001];
stack<int> s[100001];
vector<int> v[100001],f[100001];
void dfs(int poz)
{
for (vector<int>::iterator it = v[poz].begin(); it != v[poz].end(); ++it)
{
if (nod[*it].viz == 0)
{
nod[*it].viz=*it;
timp++;
nod[*it].in=timp;
dfs(*it);
timp++;
nod[*it].out=timp;
}
}
}
void dfs2(int poz)
{
for (vector<int>::iterator it = f[poz].begin(); it != f[poz].end(); ++it)
{
if (nod[*it].viz == 0)
{
nod[*it].viz=*it;
timp++;
s[k].push(*it);
nod[*it].in=timp;
dfs2(*it);
timp++;
nod[*it].out=timp;
}
}
}
bool cmp(coce a, coce b)
{
if (a.out>b.out)
return true;
else
return false;
}
int main()
{
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>a>>b;
v[a].push_back(b);
f[b].push_back(a);
}
nod[1].viz=1;
nod[1].in=1;
nod[1].out=2*n;
timp=1;
dfs(1);
sort(nod+1,nod+1+n,cmp);
for (i=1;i<=n;i++)
nod[i].viz=0;
for (i=1;i<=n;i++)
{
if (nod[i].viz==0)
{
k++;
dfs2(i);
}
}
fout<<k<<"\n";
for (i=1;i<=k;i++)
{
while (s[i].empty() == false)
{
fout<<s[i].top()<<" ";
s[i].pop();
}
fout<<"\n";
}
return 0;
}