Pagini recente » Cod sursa (job #281870) | Cod sursa (job #2154105) | Cod sursa (job #1104075) | Cod sursa (job #3263066) | Cod sursa (job #717004)
Cod sursa(job #717004)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define PB push_back
#define maxN 100005
int N , M , marked[maxN];
int pls[maxN] , mns[maxN];
vector <int> lista[maxN] , trans[maxN];
queue <int> Q;
void DFS1 (int nod , int cost)
{
pls[nod] = cost;
for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
{
int nodcur = lista[nod][i];
if (pls[nodcur] == cost)
continue;
pls[nodcur] = cost;
DFS1 (nodcur , cost);
}
}
void DFS2 (int nod , int cost)
{
mns[nod] = cost;
for (unsigned int i = 0 ; i < trans[nod].size () ; ++i)
{
int nodcur = trans[nod][i];
if (mns[nodcur] == cost)
continue;
mns[nodcur] = cost;
DFS2 (nodcur , cost);
}
}
int main ()
{
freopen ("ctc.in" , "r" , stdin);
freopen ("ctc.out" , "w" , stdout);
scanf ("%d %d" , &N , &M);
int a , b;
for (int i = 1 ; i <= M ; ++i)
{
scanf ("%d %d" , &a , &b);
lista[a].PB (b);
trans[b].PB (a);
}
int line = 0 , start;
for (int i = 1 ; i <= N ; ++i)
if (!marked[i])
{
start = i;
++line;
DFS1 (start , line);
DFS2 (start , line);
for (int i = 1 ; i <= N ; ++i)
if (pls[i] == mns[i] && pls[i] != 0)
marked[i] = pls[i];
}
printf ("%d\n" , line);
for (int i = 1 ; i <= line ; ++i)
{
for (int j = 1 ; j <= N ; ++j)
if (marked[j] == i)
printf ("%d " , j);
printf ("\n");
}
return 0;
}