Pagini recente » Cod sursa (job #2856250) | Cod sursa (job #1560888) | Cod sursa (job #984376) | Cod sursa (job #2891168) | Cod sursa (job #716947)
Cod sursa(job #716947)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define PB push_back
#define maxN 100005
int N , M , sol[maxN][100];
bool pls[maxN] , mns[maxN] , marked[maxN];
vector <int> lista[maxN] , trans[maxN];
queue <int> Q;
void BFS (vector <int> graf[maxN] , bool viz[maxN] , int start)
{
Q.push (start);
viz[start] = true;
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])
continue;
viz[nodcur] = true;
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;
marked[i] = true;
break;
}
if (done)
break;
BFS (lista , pls , start);
BFS (trans , mns , start);
++line;
for (int i = 1 ; i <= N ; ++i)
if (pls[i] && mns[i])
{
++sol[line][0];
int aux = sol[line][0];
sol[line][aux] = i;
marked[i] = true;
}
memset (pls , 0 , sizeof (pls));
memset (mns , 0 , sizeof (mns));
}
printf ("%d\n" , line);
for (int i = 1 ; i <= line ; ++i)
{
for (int j = 1 ; j <= sol[i][0] ; ++j)
printf ("%d " , sol[i][j]);
printf ("\n");
}
return 0;
}