Pagini recente » Cod sursa (job #1531195) | Cod sursa (job #3137652) | Cod sursa (job #1738312) | Cod sursa (job #1983054) | Cod sursa (job #2368460)
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> graph, connected_components;
int n, m;
void read_from_file(){
ifstream fin("ctc.in");
fin>>n>>m;
graph.resize(n+1);
int x, y;
for(int i=0; i<m; i++){
fin>>x>>y;
graph.at(x).push_back(y);
}
fin.close();
}
int idx=0, nr_ctc=0;
vector<int> low_link, id;
vector<bool> inStack, visited;
stack<int> Stack;
void Tarjan(int node){
idx++;
id.at(node) = low_link.at(node) = idx;
Stack.push(node);
inStack.at(node) = true;
for(auto& kid:graph.at(node)){
if(id.at(kid)==false) Tarjan(kid);
if(inStack.at(kid)==true){
low_link.at(node) = min(low_link.at(node), low_link.at(kid));
}
}
if(low_link.at(node)==id.at(node)){
nr_ctc++;
vector<int> component;
int x;
do{
component.push_back(x = Stack.top());
inStack.at(x) = false;
Stack.pop();
} while(x!=node);
connected_components.push_back(component);
}
}
void print_to_file(){
ofstream fout("ctc.out");
fout<<nr_ctc<<endl;
for(auto& component:connected_components){
for(auto& node:component) fout<<node<<" ";
fout<<endl;
}
}
int main()
{
read_from_file();
low_link.resize(n+1);
inStack.resize(n+1, false);
id.resize(n+1);
for(int i=1; i<=n; i++)
if(id.at(i)==0) Tarjan(i);
print_to_file();
}