Pagini recente » Cod sursa (job #1201370) | Cod sursa (job #2365351) | Cod sursa (job #3215919) | Cod sursa (job #487142) | Cod sursa (job #2636568)
#include <stdio.h>
#include <cstring>
#include <vector>
#include <stack>
#define NMAX 100005
FILE* fin, * fout;
int n, m;
std::vector<int> G[NMAX], GT[NMAX];
int nr = 0;
std::vector<int> res[NMAX];
std::stack<int> s;
bool viz[NMAX];
void dfs(int u) {
if (viz[u] == true)
return;
viz[u] = true;
for (int v : G[u])
dfs(v);
s.push(u);
}
void dfs_t(int u) {
if (viz[u] == true)
return;
viz[u] = true;
res[nr].push_back(u);
for (int v : GT[u])
dfs_t(v);
}
int main() {
fin = fopen("ctc.in", "r");
fout = fopen("ctc.out", "w");
fscanf(fin, "%i %i", &n, &m);
while (m--) {
int x, y;
fscanf(fin, "%i %i", &x, &y);
G[x].push_back(y);
GT[y].push_back(x);
}
memset(viz, false, sizeof(viz));
for (int i = 1;i <= n;++i)
dfs(i);
memset(viz, false, sizeof(viz));
while (!s.empty()) {
if (!viz[s.top()]) {
dfs_t(s.top());
++nr;
}
s.pop();
}
fprintf(fout,"%i\n", nr);
for (int i = 0;i < nr;++i) {
for (int x : res[i])
fprintf(fout,"%i ", x);
fprintf(fout,"\n");
}
return 0;
}