Pagini recente » Cod sursa (job #1546729) | Cod sursa (job #1160483) | Cod sursa (job #2498261) | Cod sursa (job #2920433) | Cod sursa (job #716996)
Cod sursa(job #716996)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
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 BFS (vector <int> graf[maxN] , int viz[maxN] , int start , int line)
{
Q.push (start);
viz[start] = line;
while (!Q.empty ())
{
int nod = Q.front ();
Q.pop ();
for (unsigned int i = 0 ; i < graf[nod].size () ; ++i)
{
int nodcur = graf[nod][i];
if (viz[nodcur] == line)
continue;
viz[nodcur] = line;
Q.push (nodcur);
}
}
}
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);
}
bool done = false;
int line = 0 , start;
while (!done)
{
done = true;
for (int i = 1 ; i <= N ; ++i)
if (!marked[i])
{
start = i;
done = false;
break;
}
if (done)
break;
++line;
BFS (lista , pls , start , line);
BFS (trans , mns , start , line);
for (int i = 1 ; i <= N ; ++i)
if (pls[i] == mns[i] && pls[i] != 0)
marked[i] = line;
}
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;
}