Pagini recente » Cod sursa (job #1690208) | Cod sursa (job #256986) | Cod sursa (job #2570973) | Cod sursa (job #684157) | Cod sursa (job #2375360)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int>> ctcs;
vector<vector<int>> graph = vector<vector<int>>(NMAX, vector<int>());
vector<int> low = vector<int>(NMAX);
vector<int> id = vector<int>(NMAX, -1);
vector<bool> inStack = vector<bool>(NMAX, false);
stack<int> st;
int idx = 0; int nr_ctc = 0;
void Tarjan(int node){
id.at(node) = low.at(node) = ++idx;
st.push(node);
inStack.at(node) = true;
for(auto& elem:graph.at(node)){
if(id.at(elem)==-1) Tarjan(elem);
if(inStack.at(elem)==true) low.at(node) = min(low.at(node), low.at(elem));
}
if(low.at(node)==id.at(node)){
int ctc_node;
vector<int> ctc;
do{
ctc_node = st.top();
st.pop();
ctc.push_back(ctc_node);
inStack.at(ctc_node) = false;
} while(ctc_node!=node);
ctcs.push_back(ctc); nr_ctc++;
}
}
int main()
{
fin>>n>>m;
int x, y;
for(int i=1; i<=m; i++){
fin>>x>>y;
graph.at(x).push_back(y);
}
for(int i=1; i<=n; i++)
if(id.at(i)==-1) Tarjan(i);
fout<<nr_ctc<<"\n";
for(auto& ctc:ctcs){
for(auto& ctc_node:ctc) fout<<ctc_node<<" ";
fout<<"\n";
}
}