Pagini recente » Cod sursa (job #1415747) | Cod sursa (job #2472874) | Cod sursa (job #1418077) | Cod sursa (job #2914514) | Cod sursa (job #1363367)
// biconex
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
#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 best[NMax], lvl[NMax];
stack< pair<int, int> > M;
vector< vector<int> > sol;
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;
while (1) {
bool ok = (M.top().first != x || M.top().second != y);
C.pb(M.top().first);
C.pb(M.top().second);
M.pop();
if (!ok) break;
if (M.empty()) 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] == 0) {
M.push(mp(node,vecin));
dfs(vecin, node);
if (best[vecin] >= lvl[node])
addComp(node, vecin);
best[node] = min(best[node], best[vecin]);
} else
best[node] = min(best[node], lvl[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();
dfs(1,0);
output();
f.close(); g.close();
return 0;
}