Pagini recente » preONI 2005 runda #1 - solutii | Cod sursa (job #842993) | Cod sursa (job #880184) | Cod sursa (job #1422514) | Cod sursa (job #2824546)
///#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
const int SIZE = 1e5+10;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
struct edge
{
int y, x;
};
int n, m;
vector <int> v[SIZE];
vector <edge> stck;
set <int> comp[SIZE];
int dfn[SIZE], low[SIZE];
int cnt, nrfii, ncnt;
void readit()
{
stck.push_back({0, 1});
int y, x;
cin>>n>>m;
for(int i=1; i<=m; i++) {
cin>>y>>x;
v[y].push_back(x);
v[x].push_back(y);
}
}
void compcon(edge ed)
{
++ncnt;
edge p = stck.back();
while(p.y!=ed.y || p.x!=ed.x) {
comp[ncnt].insert(p.y);
comp[ncnt].insert(p.x);
stck.pop_back();
p = stck.back();
}
comp[ncnt].insert(p.y);
comp[ncnt].insert(p.x);
stck.pop_back();
}
void dfs(int nod, int tnod)
{
dfn[nod] = low[nod] = ++cnt;
for(auto nxt : v[nod])
{
if(nxt!=tnod && dfn[nxt]<dfn[nod])
stck.push_back({nod, nxt});
if(!dfn[nxt])
{
dfs(nxt, nod);
low[nod] = min(low[nod], low[nxt]);
if(dfn[nod]<=low[nxt]) {
compcon({nod, nxt});
}
}
else if(nxt!=tnod)
low[nod] = min(low[nod], dfn[nxt]);
}
}
int main()
{
readit();
dfs(1, 0);
cout<<ncnt<<'\n';
for(int i=1; i<=ncnt; i++) {
for(auto j : comp[i])
cout<<j<<' ';
cout<<'\n';
}
return 0;
}