Pagini recente » Cod sursa (job #545252) | Cod sursa (job #1579678) | Cod sursa (job #1485863) | Cod sursa (job #483268) | Cod sursa (job #3039491)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
string filename = "disjoint";
#ifdef LOCAL
ifstream fin("input.in");
ofstream fout("output.out");
#else
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
#endif
const int NMAX = 1e5;
vector <int> adj[NMAX + 1];
vector <int> r[NMAX + 1];
vector <int> topo;
bool viz[NMAX + 1];
void dfs(int node){
viz[node] = true;
for(int vec : adj[node]){
if(!viz[vec]){
dfs(vec);
}
}
topo.push_back(node);
}
vector <vector <int>> comps;
vector <int> aux;
void dfs2(int node){
viz[node] = true;
aux.push_back(node);
for(int vec : r[node]){
if(!viz[vec]){
dfs2(vec);
}
}
}
signed main(){
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++){
int a, b;
fin >> a >> b;
adj[a].push_back(b);
r[b].push_back(a);
}
for(int i = 1; i <= n; i++){
if(!viz[i]){
dfs(i);
}
}
reverse(topo.begin(), topo.end());
for(int i = 1; i <= n; i++){
viz[i] = false;
}
for(int i = 0; i < (int)topo.size(); i++){
if(!viz[topo[i]]){
aux.clear();
dfs2(topo[i]);
comps.push_back(aux);
}
}
fout << (int)comps.size() << '\n';
for(int i = 0; i < (int)comps.size(); i++){
sort(comps[i].begin(), comps[i].end());
for(int x : comps[i]){
fout << x << ' ';
}
fout << '\n';
}
return 0;
}