Pagini recente » Cod sursa (job #2256221) | Cod sursa (job #1723030) | Cod sursa (job #1701775) | Cod sursa (job #2940709) | Cod sursa (job #2665927)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m, i, j, ord[100005], niv_min[100005];
bool viz[100005];
vector<int> v[100005], t(100005, -1);
vector<vector<int>> comp;
stack<int> st;
void dfs(int nod) {
int it, x;
vector<int> c;
viz[nod] = true;
ord[nod] = ord[t[nod]] + 1; /// ordinea de vizitare; pt fiecare nod, va fi ord[tata] + 1
niv_min[nod] = ord[nod]; /// nivelul min la care ma pot intoarce este al meu
st.push(nod); /// adaug nodul pe stiva
for(it = 0; it < v[nod].size(); it++) /// parcurg vecinii nodului curent
if(viz[v[nod][it]]) {
if(v[nod][it] != t[nod]) /// daca a fost vizitat si nu este tatul lui nod, actualizez niv_min
niv_min[nod] = min(niv_min[nod], ord[v[nod][it]]);
}
else { /// daca vecinul nu a fost vizitat
t[v[nod][it]] = nod; /// actualizez tatal si apelez dfs()
dfs(v[nod][it]);
niv_min[nod] = min(niv_min[nod], niv_min[v[nod][it]]); /// actualizez niv_min
if(ord[nod] <= niv_min[v[nod][it]]) { /// nodul curent este critic
c.clear();
while(!st.empty()) {
x = st.top();
st.pop();
c.push_back(x);
if(x == v[nod][it]) { /// toate nodurile din stiva, care sunt deasupra vecinului curent sunt in componenta biconexa, la care se adauga nodul critic gasit
c.push_back(nod);
comp.push_back(c);
break;
}
}
}
}
}
int main() {
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> n >> m;
while(m) {
f >> i >> j;
v[i].push_back(j);
v[j].push_back(i);
m--;
}
f.close();
for(i = 1; i <= n; i++)
if(!ord[i]) {
t[i] = 0;
dfs(i);
}
g << comp.size() << '\n';
for(i = 0; i < comp.size(); i++, g << '\n')
for(j = 0; j < comp[i].size(); j++)
g << comp[i][j] << ' ';
g.close();
return 0;
}