Pagini recente » Cod sursa (job #254460) | Cod sursa (job #2707762) | Cod sursa (job #1739885) | Cod sursa (job #819671) | Cod sursa (job #1487912)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
const int N = 100002;
vector <int> graph [N], graph2 [N], CTC [N];
stack <int> st;
bool used [N];
int ctc [N], ob;
void dfs (int x) {
vector <int> :: iterator it;
used [x] = 1;
for (it = graph [x].begin (); it != graph [x].end (); ++ it)
if (!used [*it])
dfs (*it);
st.push (x);
}
void dfs2 (int x) {
vector <int> :: iterator it;
ctc [x] = ob;
CTC [ob].push_back (x);
for (it = graph2 [x].begin (); it != graph2 [x].end (); ++ it)
if (!ctc [*it])
dfs2 (*it);
}
int main () {
int i, n, a, b, m;
vector <int> :: iterator it;
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
scanf ("%d%d", &n, &m);
for (i = 1; i <= m; i ++) {
scanf ("%d%d", &a, &b);
graph [a].push_back (b);
graph2 [b].push_back (a);
}
for (i = 1; i <= n; i ++)
if (!used [i])
dfs (i);
ob = 0;
while (!st.empty ()) {
i = st.top ();
st.pop ();
if (!ctc [i]) {
++ ob;
dfs2 (i);
}
}
printf ("%d\n", ob);
for (i = 1; i <= ob; i ++) {
for (it = CTC [i].begin (); it != CTC [i].end (); ++ it)
printf ("%d ", *it);
printf ("\n");
}
return 0;
}