Pagini recente » Cod sursa (job #3228624) | Cod sursa (job #2344714) | Cod sursa (job #2096614) | Cod sursa (job #1084795) | Cod sursa (job #1363153)
// biconex
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>
#define mp make_pair
#define pb push_back
#define NMax 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector<int> V[NMax];
stack< pair<int, int> > M; // Muchii
int lvl[NMax];
int best[NMax];
vector< vector<int> > comps;
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) {
cout<<x<<' '<<y<<endl;
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());
auto it = unique(C.begin(), C.end());
C.erase(it, C.end());
comps.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) {
M.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], lvl[vecin]);
}
}
}
void output() {
g<<comps.size()<<'\n';
for (unsigned i=0;i<comps.size();i++) {
for (unsigned j=0;j<comps[i].size();j++)
g<<comps[i][j]<<' ';
g<<'\n';
}
}
int main() {
read();
memset(lvl, -1, sizeof(lvl));
dfs(1,0);
output();
f.close(); g.close();
return 0;
}