Pagini recente » Cod sursa (job #314558) | Cod sursa (job #3128036) | Cod sursa (job #2607920) | Cod sursa (job #1424710) | Cod sursa (job #2927001)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> adj_list;
vector<int> indx; //retine indexul atribuit fiecarui nod in urma parcurgerii DFS
//ce numără nodurile în ordinea în care sunt descoperite
vector<int> lowlink;
//lowlink[v] = min { idx[u] | u este accesibil din v }. v rad <=> lowlink[v] = idx[v]. lowlink[v]
vector <bool> onStack;
stack <int> st;
int id = 0; // da fiecarui nod un id
int sccCount = 0;//contorizeaza componentele tare conexe
vector<vector<int>> scc;
//algoritmul lui tarjan
void dfs(int node){
st.push(node);
onStack[node] = true;
indx[node] = lowlink[node] = ++id;
//vizitam toti vecinii nodului si calculam min dintre valorile atribuite in lowlink
for(auto x : adj_list[node]){
if(indx[x] == -1)
dfs(x);
if(onStack[x])
lowlink[node] = min(lowlink[node], lowlink[x]);
}
//dupa ce am vizitat toti vecinii nodului
//daca suntem la inceputul unei ctc
//stiva va fi golita pana suntem la inceputul ctc
if(indx[node] == lowlink[node]){
vector<int> ctc;
int nod = st.top();
while(nod != node){
st.pop();
onStack[nod] = false;
lowlink[nod] = indx[node];
ctc.push_back(nod);
nod = st.top();
}
st.pop();
ctc.push_back(node);
scc.push_back(ctc);
onStack[node] = false;
sccCount++;
}
}
int main(){
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y;
fin >> n >> m;
adj_list.resize(n+1);
for(int i = 0; i < m; ++i){
fin >> x >> y;
adj_list[x].push_back(y);
}
indx = vector<int>(n + 1,-1);
lowlink = vector<int>(n + 1,-1);
onStack = vector<bool>(n + 1,false);
for(int i = 1; i < n+1; ++i)
if(indx[i] == -1)
dfs(i);
fout<<sccCount<<"\n";
for(auto x: scc) {
for (auto y: x)
fout << y << " ";
fout<<"\n";
}
}