Pagini recente » Cod sursa (job #1717358) | Cod sursa (job #2464710) | Cod sursa (job #3251202) | Cod sursa (job #588690) | Cod sursa (job #2263793)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 100001
#define pb push_back
#define mp make_pair
vector <int> v[NMAX],sol[2*NMAX];
vector < pair < int , int > > st;
int viz[NMAX],l[NMAX],dfn[NMAX],nrc;
inline void bc(int x, int y)
{
nrc++;
int a,b;
do {
a=st.back().first;
b=st.back().second;
st.pop_back();
sol[nrc].pb(a);
sol[nrc].pb(b);
}
while(x!=a || y!=b);
}
inline void dfs(int nod, int tata, int niv)
{
viz[nod]=1;
l[nod]=niv;
dfn[nod]=niv;
for(vector <int> :: iterator it=v[nod].begin();it!=v[nod].end();it++) {
if(*it==tata)
continue;
if(viz[*it]==0) {
st.pb(mp(nod,*it));
dfs(*it,nod,niv+1);
l[nod]=min(l[nod],l[*it]);
if(l[*it]>=niv)
bc(nod,*it);
}
else l[nod]=min(l[nod],dfn[*it]);
}
}
int main ()
{
int n,m,x,y,i,j;
ifstream f("biconex.in");
ofstream g("biconex.out");
f>>n>>m;
for(i=1;i<=m;i++) {
f>>x>>y;
v[x].pb(y);
v[y].pb(x);
}
f.close();
dfs(1,0,0);
g<<nrc<<'\n';
for(i=1;i<=nrc;i++) {
sort(sol[i].begin(),sol[i].end());
n=sol[i].size()-1;
g<<sol[i][0]<<" ";
for(j=1;j<=n;j++)
if(sol[i][j]!=sol[i][j-1])
g<<sol[i][j]<<" ";
g<<'\n';
}
g.close();
return 0;
}