Pagini recente » Cod sursa (job #319578) | Cod sursa (job #3162096) | Cod sursa (job #1392898) | Cod sursa (job #330654) | Cod sursa (job #2668648)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 1e5+5;
vector<int> graf[NMAX];
int niv[NMAX], low[NMAX];
bool vis[NMAX], use[NMAX];
vector<vector<int> > sol;
stack<pair<int,int> > Edges;
void CompBiconexa(int x, int y) {
vector<int> c;
pair<int,int> m, m1 = make_pair(x, y), m2 = make_pair(y, x);
do {
m = Edges.top();
c.push_back(m.first);
c.push_back(m.second);
Edges.pop();
} while(m != m1 && m != m2);
sol.push_back(c);
}
void dfs(int nod, int tata) {
vis[nod] = 1;
low[nod] = niv[nod];
for(int i = 0; i < (int)graf[nod].size(); i++) {
int next = graf[nod][i];
if(next != tata && niv[nod] > niv[next]) {
Edges.push(make_pair(next, nod));
}
if(!vis[next]) {
niv[next] = niv[nod] + 1;
dfs(next, nod);
low[nod] = min(low[nod], low[next]);
if(low[next] >= niv[nod]) {
CompBiconexa(next, nod);
}
} else {
if(next != tata && low[nod] > niv[next]) {
low[nod] = niv[next];
}
}
}
}
int main()
{
int n, m;
f >> n >> m;
while(m--) {
int x, y;
f >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
niv[1] = 1;
dfs(1, 0);
g << sol.size() << '\n';
for(int i = 0 ; i < (int)sol.size(); i++) {
for(int j = 0; j < (int)sol[i].size(); j++) {
use[sol[i][j]] = 1;
}
for(int j = 0; j < (int)sol[i].size(); j++) {
if(use[sol[i][j]] == 1) {
g << sol[i][j] << ' ';
use[sol[i][j]] = 0;
}
}
g << '\n';
}
return 0;
}