Pagini recente » Cod sursa (job #2332473) | Cod sursa (job #923527) | Cod sursa (job #1094696) | Cod sursa (job #1587113) | Cod sursa (job #748565)
Cod sursa(job #748565)
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define maxN 100005
#define PB push_back
int N , M , dim , a , b;
bool viz[maxN];
vector <int> lista[maxN] , lista2[maxN] , Q , sol[maxN];
void DFS (int nod)
{
if (viz[nod])
return;
viz[nod] = true;
for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
{
int nodcur = lista[nod][i];
if (viz[nodcur])
continue;
DFS (nodcur);
}
Q.PB (nod);
}
void DFS2 (int nod)
{
if (viz[nod])
return;
viz[nod] = true;
sol[dim].PB (nod);
for (unsigned int i = 0 ; i < lista2[nod].size () ; ++i)
{
int nodcur = lista2[nod][i];
if (viz[nodcur])
continue;
DFS2 (nodcur);
}
}
void Korsaju ()
{
memset (viz , 0 , sizeof (viz));
for (int i = Q.size () - 1 ; i >= 0 ; --i)
{
if (viz[Q[i]])
continue;
++dim;
DFS2 (Q[i]);
}
}
int main ()
{
freopen ("ctc.in" , "r" , stdin);
freopen ("ctc.out" , "w" , stdout);
scanf ("%d %d" , &N , &M);
while (M --)
{
scanf ("%d %d" , &a , &b);
lista[a].PB (b);
lista2[b].PB (a);
}
for (int i = 1 ; i <= N ; ++i)
{
if (viz[i])
continue;
DFS (i);
}
Korsaju ();
printf ("%d\n" , dim);
for (int i = 1 ; i <= dim ; ++i)
{
for (unsigned int j = 0 ; j < sol[i].size () ; ++j)
printf ("%d " , sol[i][j]);
printf ("\n");
}
return 0;
}