Pagini recente » Cod sursa (job #811855) | Cod sursa (job #1987674) | Cod sursa (job #302202) | Cod sursa (job #1108626) | Cod sursa (job #1003401)
#include <cstdio>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;
const int NMAX = 100003;
vector <int> G[NMAX], Gt[NMAX], R[NMAX];
stack <int> S;
bitset <NMAX> viz;
int s;
void topological_sort (const int &node) {
vector <int> :: iterator i;
viz[node] = 1;
for (i = G[node].begin (); i != G[node].end (); ++i)
if (!viz[*i])
topological_sort (*i);
S.push (node);
}
void DFST (const int &node) {
vector <int> :: iterator i;
viz[node] = 0;
R[s].push_back (node);
for (i = Gt[node].begin (); i != Gt[node].end (); ++i)
if (viz[*i])
DFST (*i);
}
int main () {
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
int N, M, i, a, b;
vector <int> :: iterator j;
scanf ("%d%d", &N, &M);
for (i = 1; i <= M; ++i)
scanf ("%d%d", &a, &b),
G[a].push_back (b),
Gt[b].push_back (a);
for (i = 1; i <= N; ++i)
if (!viz[i])
topological_sort (i);
while (!S.empty ()) {
a = S.top ();
S.pop ();
if (viz[a])
++s,
DFST (a);
}
printf ("%d\n", s);
for (i = 1; i <= s; ++i) {
for (j = R[i].begin (); j != R[i].end (); ++j)
printf ("%d ", *j);
printf ("\n");
}
}