Pagini recente » Cod sursa (job #483580) | Cod sursa (job #1628369) | Cod sursa (job #1094267) | Cod sursa (job #548219) | Cod sursa (job #306949)
Cod sursa(job #306949)
#include <cstdio>
#include <vector>
#define maxn 100100
using namespace std;
vector <int> g[maxn], gi[maxn];
int n, m, a, b, i, j, nrc, comp;
int st[maxn], sz, viz[maxn];
vector <int> sol[maxn];
void dfp(int nod) {
int fiu, i;
if (viz[nod])
return;
viz[nod] = 1;
for (i = 0; i < g[nod].size(); i++) {
fiu = g[nod][i];
dfp(fiu);
}
sz++;
st[sz] = nod;
}
void dfm(int nod, int comp) {
int fiu, i;
if (viz[nod])
return;
viz[nod] = 1;
sol[comp].push_back(nod);
for (i = 0; i < gi[nod].size(); i++) {
fiu = gi[nod][i];
dfm(fiu, comp);
}
}
int main() {
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);
g[a].push_back(b);
gi[b].push_back(a);
}
for (i = 1; i <= n; i++)
dfp(i);
memset(viz, 0, sizeof(viz));
/* for (i = 1; i <= sz; i++)
printf("%d ", st[i]);
printf("\n");*/
for (i = sz; i > 0; i--) {
if (!viz[st[i]]) {
comp++;
fprintf(stderr, "%d\n", st[i]);
dfm(st[i], comp);
}
}
printf("%d\n", comp);
for (i = 1; i <= comp; i++) {
for (j = 0; j < sol[i].size(); j++)
printf("%d ", sol[i][j]);
printf("\n");
}
return 0;
}