Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 208 si 223 | Cod sursa (job #3286791) | Diferente pentru implica-te/arhiva-educationala intre reviziile 175 si 223 | Istoria paginii clasament-arhiva-educationala | Cod sursa (job #3286598)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int LMAX = 200005;
const int MOD = 1000000007;
const int INF = 0x3F3F3F3F;
vector<int> L[LMAX], LT[LMAX], order, comp[LMAX];
vector<bool> viz;
void dfs(int node) {
viz[node] = 1;
for (int vec : L[node]) {
if (!viz[vec]) dfs(vec);
}
order.push_back(node);
}
void dfs2(int node, int nr_comp) {
viz[node] = 1;
comp[nr_comp].push_back(node);
for (int vec : LT[node]) {
if (!viz[vec]) {
dfs2(vec, nr_comp);
}
}
}
int main() {
int n, m, i;
fin>>n>>m;
while (m--) {
int x, y;
fin>>x>>y;
L[x].push_back(y);
LT[y].push_back(x);
}
viz.assign(n + 5, 0);
//sortez topologic
for (i = 1; i <= n; i++) {
if (!viz[i]) {
dfs(i);
}
}
reverse(order.begin(), order.end());
viz.assign(n + 5, 0);
int nr_comp = 1;
for (i = 1; i <= n; i++) {
if (!viz[i]) {
dfs2(i, nr_comp);
if (comp[nr_comp].size() > 1) {
nr_comp++;
}
else {
comp[nr_comp].pop_back();
}
}
}
fout<<nr_comp - 1<<"\n";
for (i = 1; i < nr_comp; i++) {
for (int vec : comp[i]) {
fout<<vec<<" ";
}
fout<<"\n";
}
fin.close();
fout.close();
return 0;
}