Pagini recente » Cod sursa (job #2212177) | Cod sursa (job #874068) | Cod sursa (job #2535706) | Cod sursa (job #1477602) | Cod sursa (job #2928892)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, y, x, viz[100000], nrComp;
vector<vector<int>> lista, transp, comp;
vector<int> s, v;
void dfs1(int x) {
viz[x] = 1;
for (auto i : lista[x])
if (!viz[i]) dfs1(i);
s.push_back(x);
}
void dfs2(int x) {
viz[x] = 0;
comp[nrComp].push_back(x);
for (auto i : transp[x])
if (viz[i])
dfs2(i);
}
int main() {
fin >> n >> m;
lista = transp = vector<vector<int>>(n);
for (int i = 0; i < m; i++) {
fin >> x >> y;
lista[x - 1].push_back(y - 1);
transp[y - 1].push_back(x - 1);
}
for (int i = 0; i < n; i++)
if (!viz[i]) dfs1(i);
while (!s.empty()) {
x = s.back();
s.pop_back();
if (viz[x]) {
comp.push_back(v);
dfs2(x);
nrComp++;
}
}
fout << nrComp << '\n';
for (auto v : comp) {
for (auto i : v) fout << i + 1 << " ";
fout << '\n';
}
}