Pagini recente » Cod sursa (job #1986447) | Cod sursa (job #2499961) | Cod sursa (job #1366354)
// biconex
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define pb push_back
#define mp make_pair
#define NMax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m;
vector<int> V[NMax];
int lvl[NMax], best[NMax];
vector< vector<int> > sol;
stack< pair<int, int> > muc;
void read() {
f>>n>>m;
for (int i=1;i<=m;i++) {
int a,b;
f>>a>>b;
V[a].pb(b);
V[b].pb(a);
}
}
void addComp(int x, int y) {
vector<int> c; c.resize(0);
while (1) {
int nod1 = muc.top().first;
int nod2 = muc.top().second;
muc.pop();
c.pb(nod1); c.pb(nod2);
if (muc.empty()) break;
if (nod1 == x && nod2 == y) break;
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
sol.pb(c);
}
void dfs(int node, int father) {
best[node] = lvl[node] = lvl[father]+1;
for (unsigned i=0;i<V[node].size();i++) {
int vecin = V[node][i];
if (vecin == father) continue;
if (lvl[vecin] == -1) {
muc.push(mp(node, vecin));
dfs(vecin, node);
best[node] = min(best[node], best[vecin]);
if (best[vecin] >= lvl[node])
addComp(node, vecin);
} else
best[node] = min(best[node], best[vecin]);
}
}
void output() {
g<<sol.size()<<'\n';
for (unsigned i=0;i<sol.size();i++) {
for (unsigned j=0;j<sol[i].size();j++)
g<<sol[i][j]<<' ';
g<<'\n';
}
}
int main() {
read();
memset(lvl, -1, sizeof(lvl));
dfs(1,0);
output();
f.close(); g.close();
return 0;
}