Pagini recente » Cod sursa (job #230483) | Cod sursa (job #2350813) | Cod sursa (job #1086391) | Cod sursa (job #2641113) | Cod sursa (job #3296203)
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
vector<int> v[MAXN + 1];
vector<int> vtr[MAXN + 1];
vector<int> ctc[MAXN + 1];
char f[MAXN + 1];
int post[MAXN];
int nrn, nrc;
void dfs(int nod) {
int i, x, nr;
f[nod] = 1;
nr = v[nod].size();
for (i = 0; i < nr; i++) {
x = v[nod][i];
if (f[x] == 0) {
dfs(x);
}
}
post[nrn] = nod;
nrn++;
}
void dfs2(int nod) {
int i, x, nr;
f[nod] = 1;
ctc[nrc].push_back(nod);
nr = vtr[nod].size();
for (i = 0; i < nr; i++) {
x = vtr[nod][i];
if (f[x] == 0) {
dfs2(x);
}
}
}
int main()
{
FILE *fin, *fout;
int n, m, i, x, y, nr, nod, j;
fin = fopen("ctc.in", "r");
fscanf(fin, "%d%d", &n, &m);
for (i = 0; i < m; i++) {
fscanf(fin, "%d%d", &x, &y);
v[x].push_back(y);
vtr[y].push_back(x);
}
fclose(fin);
for (i = 1; i <= n; i++) {
if (f[i] == 0) {
dfs(i);
}
}
for (i = 1; i <= n; i++) {
f[i] = 0;
}
//al doilea dfs
nrc = 0;
for (i = n - 1; i >= 0; i--) {
if (f[post[i]] == 0) {
dfs2(post[i]);
nrc++;
}
}
fout = fopen("ctc.out", "w");
fprintf(fout, "%d\n", nrc);
for (i = 0; i < nrc; i++) {
nr = ctc[i].size();
for (j = 0; j < nr; j++) {
fprintf(fout, "%d ", ctc[i][j]);
}
fputc('\n', fout);
}
fclose(fout);
return 0;
}