Pagini recente » Cod sursa (job #1920470) | Cod sursa (job #1702432) | Cod sursa (job #2670217) | Cod sursa (job #857774) | Cod sursa (job #3003664)
//tare conex
#include <fstream>
#include <vector>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int n;
std::vector<std::vector<int>> V, GT, comp_biconex;
std::vector<int> postorder, viz;
void postDFS(int u){
viz[u] = true;
for(auto v : V[u]){
if(!viz[v]){
postDFS(v);
}
}
postorder.push_back(u);
}
int cnt;
void DFS(int u){
viz[u] = true;
comp_biconex[cnt].push_back(u);
for(auto v : GT[u]){
if(!viz[v]){
DFS(v);
}
}
}
int main(){
int n, m;
fin >> n >> m;
V = GT = comp_biconex = std::vector<std::vector<int>> (n + 1, std::vector<int> ());
viz = std::vector<int> (n + 1, 0);
for(int u, v, i = 1; i <= m; i++){
fin >> u >> v;
V[u].push_back(v);
GT[v].push_back(u);
}
for(int i = 1; i <= n; i++){
if(!viz[i]){
postDFS(i);
}
}
viz = std::vector<int> (n + 1, 0);
for(int i = n - 1; i > 0; i--){
if(!viz[postorder[i]]){
DFS(postorder[i]);
++cnt;
}
}
fout << cnt << "\n";
for(int i = 0; i < cnt; i++){
for(auto it : comp_biconex[i])
fout << it << " ";
fout << "\n";
}
}