Pagini recente » Cod sursa (job #2518622) | Cod sursa (job #2512259) | Cod sursa (job #555354) | Cod sursa (job #784577) | Cod sursa (job #410253)
Cod sursa(job #410253)
#include <algorithm>
#include <vector>
#include <stack>
#define nmax 100005
using namespace std;
int n,m,i,x,y,k;
vector <int> viz, viz2;
vector <int> G[nmax], Gt[nmax], Gs[nmax];
vector <int>::iterator it;
vector <int> s;
void df(int x)
{
vector <int>::iterator it;
viz[x]=true;
for (it=G[x].begin();it!=G[x].end();++it)
if (viz[*it]==false)
df(*it);
s.push_back(x);
}
void dft(int x)
{
vector <int>::iterator it;
viz2[x]=k;
for (it=Gt[x].begin();it!=Gt[x].end();++it)
if (viz2[*it]==-1)
dft(*it);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;i++)
{
scanf("%d %d", &x, &y);
x --; y --;
G[x].push_back(y);
Gt[y].push_back(x);
}
viz.resize(n);
viz.assign(viz.size(),0);
for (i=0;i<n;i++)
if (viz[i]==false)
df(i);
k=0;
viz2.resize(n);
viz2.assign(viz2.size(),-1);
for (; s.size(); s.pop_back())
if (viz2[s.back()]==-1)
{
dft(s.back());
k++;
}
for (i=0;i<n;++i)
Gs[viz2[i]].push_back(i);
printf("%d\n", k);
for (i=0;i<k;i++)
{
for (it=Gs[i].begin();it!=Gs[i].end();++it)
printf("%d ", *it+1);
printf("\n");
}
return 0;
}