Pagini recente » Rating Mariciuc Andrei-Alexandru (Andrei1) | Monitorul de evaluare | Statistici Bahna Cosmina (cosminabahna) | Istoria paginii utilizator/sebivista | Cod sursa (job #2003262)
#include <bits/stdc++.h>
#define MAXN 100000
std::vector <int> g[MAXN + 1];
bool viz[MAXN + 1];
int lvl[MAXN + 1];
int low[MAXN + 1];
std::stack <int> stk;
std::vector <int> sol[MAXN + 1];
int cnt = 0;
void dfs(int nod) {
viz[nod] = 1;
stk.push(nod);
for(auto it : g[nod])
if(viz[it] == 0) {
lvl[it] = lvl[nod] + 1;
low[it] = lvl[nod] + 1;
dfs(it);
if(low[it] >= lvl[nod]) {
cnt++;
while(stk.top() != it) {
sol[cnt].push_back(stk.top());
stk.pop();
}
stk.pop();
sol[cnt].push_back(it);
sol[cnt].push_back(nod);
}
low[nod] = std::min(low[nod], low[it]);
}
else
low[nod] = std::min(low[nod], lvl[it]);
}
int main() {
FILE *fi, *fout;
int i, n, m, x, y;
fi = fopen("biconex.in" ,"r");
fout = fopen("biconex.out" ,"w");
fscanf(fi,"%d %d " ,&n,&m);
for(i = 1; i <= m; i++) {
fscanf(fi,"%d %d " ,&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(i = 1; i <= n; i++)
if(viz[i] == 0)
dfs(i);
fprintf(fout,"%d\n" ,cnt);
for(i = 1; i <= cnt; i++) {
for(auto it : sol[i])
fprintf(fout,"%d " ,it);
fprintf(fout,"\n");
}
fclose(fi);
fclose(fout);
return 0;
}