Pagini recente » Cod sursa (job #3204932) | Cod sursa (job #8474) | Cod sursa (job #396731) | Cod sursa (job #3135836) | Cod sursa (job #2927853)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, u, v, ind_var;
int nr_componente;
vector<bool> onStack(100005); // daca nodul mai e pe stack
vector<int> ind(100005); // ordinea de vizitare a nodurilor
vector<int> lowlink(100005); // indexul cel mai mic al unui nod din componenta tare conexa
vector<vector<int>> ad(100005); // lista de adiacente
vector<vector<int>> result(100005);
stack<int> st;
void dfs(int node){
ind_var ++;
ind[node] = ind_var;
lowlink[node] = ind_var;
st.push(node);
onStack[node] = true;
// parcurg vecinii & update lowlink
for(auto vec : ad[node]) {
if (ind[vec] == 0) {
dfs(vec);
lowlink[node] = min(lowlink[node], lowlink[vec]);
} else if (onStack[vec])
lowlink[node] = min(lowlink[node], lowlink[vec]);
}
if(ind[node] == lowlink[node]) {
// este inceputul unei componente tare conexe
// in stiva vor fi restul componentelor componentei conexe
nr_componente ++;
u = st.top();
while(node != u) // adaugam componenta la result
{
result[nr_componente].push_back(u);
onStack[u] = false;
st.pop();
u = st.top();
}
result[nr_componente].push_back(u);
st.pop();
onStack[u] = false;
}
}
int main()
{
fin >> n >> m;
// lista de adiacente
for(int i = 1; i <= m; i ++){
fin >> u >> v;
ad[u].push_back(v);
}
ind_var = 0;
for(int i = 1; i <= n; i ++){
if(ind[i] == 0){
dfs(i);
}
}
fout << nr_componente << '\n';
for(int i = 1; i <= nr_componente; i ++) {
for(auto node : result[i])
fout << node << " ";
fout << '\n';
}
}