Pagini recente » Cod sursa (job #1768133) | Cod sursa (job #1153120) | Cod sursa (job #2546774) | Cod sursa (job #2090802) | Cod sursa (job #1909538)
#include <bits/stdc++.h>
#define nmax 100002
using namespace std;
vector <int> v[nmax], vt[nmax];
vector <int> postordine;
int viz[nmax];
void DFS (int x)
{
viz[x]=1;
vector <int> :: iterator it;
for (it=v[x].begin();it!=v[x].end(); ++it)
if (!viz[*it]) DFS(*it);
postordine.push_back(x);
}
vector <int> sol[nmax];
void DFST (int x, int y)
{
vector <int> :: iterator it;
sol[y].push_back(x);
viz[x]=0;
for (it=vt[x].begin();it!=vt[x].end();++it)
if (viz[*it]) DFST(*it,y);
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, i, j;
f >> n >> m;
int x, y;
for (i=1;i<=m; ++i)
{
f >> x >> y;
v[x].push_back(y);
vt[y].push_back(x);
}
for (i=1; i<=n; ++i)
if (!viz[i]) DFS(i);
y=0;
vector <int> :: reverse_iterator it;
for (it=postordine.rbegin();it!=postordine.rend();++it)
if (viz[*it]) DFST(*it,++y);
g << y << "\n";
for (i=1; i<=y; ++i)
{
vector <int> :: iterator it;
for (it=sol[i].begin();it!=sol[i].end();++it)
g << *it << " ";
g << "\n";
}
return 0;
}