Pagini recente » Cod sursa (job #496126) | Cod sursa (job #1169440) | Cod sursa (job #550863) | Cod sursa (job #114103) | Cod sursa (job #824699)
Cod sursa(job #824699)
#include <fstream>
#include <cstring>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, K;
int S[NMAX];
int U[NMAX];
struct list {
int inf;
list *next;
};
list *G[NMAX];
list *GT[NMAX];
void add(int a, int b, int arg) {
list *q = new list;
q->inf = b;
if(!arg) {
q->next = G[a];
G[a] = q;
} else {
q->next = GT[a];
GT[a] = q;
}
}
void read() {
int i, a, b;
fin >> N >> M;
for(i = 1; i <= M; ++i) {
fin >> a >> b;
add(a, b, 0);
add(b, a, 1);
}
}
void dfs(int nod) {
list *it;
U[nod] = 1;
for(it = G[nod]; it; it = it->next)
if(!U[it->inf])
dfs(it->inf);
S[++K] = nod;
}
void dfsT(int nod, int arg) {
list *it;
U[nod] = 1;
if(arg) fout << nod << ' ';
for(it = GT[nod]; it; it = it->next)
if(!U[it->inf])
dfsT(it->inf, arg);
}
void solve() {
int i, count = 0;
for(i = 1; i <= N; ++ i)
if(!U[i]) dfs(i);
memset(U, 0, sizeof(U));
for(i = K; i >= 1; --i)
if(!U[S[i]]) {
++count;
dfsT(S[i], 0);
}
fout << count << '\n';
memset(U, 0, sizeof(U));
for(i = K; i >= 1; -- i)
if(!U[S[i]]) {
dfsT(S[i], 1);
fout << '\n';
}
}
int main() {
read();
solve();
return 0;
}