Pagini recente » Cod sursa (job #2814812) | Cod sursa (job #1696390) | Cod sursa (job #53957) | Cod sursa (job #691506) | Cod sursa (job #2928828)
///Problema 4 O(n + m) - Tarjan
///Link:
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
vector<vector<int>> lista;
vector<int> viz,ids,lw;
vector<bool> st;
stack<int> stiva;
int contor = 1, cc = 1;
unordered_map<int, vector<int>> ccs;
void DFS(int nod){
ids[nod] = contor++;
lw[nod] = ids[nod];
viz[nod] = 1;
st[nod] = true;
stiva.push(nod);
for(auto& i:lista[nod]){
if(!viz[i]){
DFS(i);
}
if(st[i])
lw[nod] = min(lw[nod], lw[i]);
}
if(ids[nod] == lw[nod]){
int popped;
vector<int> aux;
do{
popped = stiva.top();
stiva.pop();
st[popped] = false;
aux.push_back(popped);
}while(popped != nod);
ccs[cc++] = aux;
}
}
int main()
{
int n,m,x,y;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin>>n>>m;
lista.resize(n+1);
for(int i = 1; i <= m; i++){
fin>>x>>y;
lista[x].push_back(y);
}
viz.resize(n+1, 0);
st.resize(n+1, false);
ids.resize(n+1, 0);
lw.resize(n+1, 0);
DFS(1);
fout<<cc - 1<<endl;
for(int i = 1; i < cc; i++){
for(auto& j:ccs[i]){
fout<<j<<" ";
}
fout<<endl;
}
fin.close();
fout.close();
return 0;
}