Pagini recente » Cod sursa (job #1065883) | Cod sursa (job #1599840) | Cod sursa (job #1613066) | Cod sursa (job #1296669) | Cod sursa (job #1492284)
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
int viz[100005];
int viz2[100005];
int v[100005];
struct node{
node *next;
int inf;
};
node *L[100005];
node *K[100005];
void add(node *&start, int inf) {
node *one = new node;
one->inf = inf;
one->next = start;
start = one;
}
void dfs(int in) {
viz[in] = true;
for(node *p = L[in]; p; p = p->next) {
if(!viz[p->inf])
dfs(p->inf);
}
}
void dfs2(int in) {
viz2[in] = true;
for(node *p = K[in]; p; p = p->next) {
if(!viz2[p->inf])
dfs2(p->inf);
}
}
int main()
{
FILE *f = fopen("ctc.in", "r");
FILE *g = fopen("ctc.out", "w");
fscanf(f, "%d %d", &n, &m);
for(int i = 1; i <= m; i ++) {
fscanf(f, "%d %d", &x, &y);
add(L[x], y);
add(K[y], x);
}
int nr = 0;
for(int i = 1; i <= n; i ++) {
if(!v[i]) {
nr ++;
dfs(i);
dfs2(i);
for(int j = 1; j <= n; j ++) {
if(viz[j] == 1 && viz2[j] == 1) {
v[j] = nr;
viz[j] = 2;
viz2[j] = 2;
}
else viz[j] = 0, viz2[j] = 0;
}
}
}
fprintf(g, "%d\n", nr);
while(nr) {
for(int i = 1; i <= n; i ++) {
if(v[i] == nr)
fprintf(g, "%d ", i);
}
fprintf(g, "\n");
nr --;
}
return 0;
}