Pagini recente » Cod sursa (job #2966907) | Cod sursa (job #2562496) | Cod sursa (job #1769650) | Cod sursa (job #290488) | Cod sursa (job #1506712)
using namespace std;
#include <fstream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#define Maxn 100005
#define Min(a,b)((a)<(b)? (a):(b))
ifstream f ("biconex.in");
ofstream g ("biconex.out");
vector<int> adj[Maxn],dfn,low;
vector<vector<int> >C;
stack < pair < int,int > >stk;
void read (int &n)
{
int m,x,y;
f>>n>>m;
while(m--)
{
f>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void cache_bc(int x,int y)
{
vector<int> con;
int tx,ty;
do
{
tx=stk.top().first;
ty=stk.top().second;
stk.pop();
con.push_back(tx);
con.push_back(ty);
}
while(tx!=x || ty!=y);
C.push_back(con);
}
void DF(int n, int fn, int number)
{
vector<int>::iterator it;
dfn[n]=low[n]=number;
for(it=adj[n].begin(); it!=adj[n].end(); it++)
{
if(*it==fn) continue;
if(dfn[*it]==-1)
{
stk.push(make_pair(n,*it));
DF(*it,n,number+1);
low[n]=Min(low[n],low[*it]);
if(low[*it]>=dfn[n]) //n e punct de articulatie
cache_bc(n,*it);
}
else low[n]=Min(low[n],dfn[*it]); //[n,*it] e muchie de intoarcere de la n la *it
}
}
int main()
{
int n;
read(n);
dfn.resize(n+1);
dfn.assign(n+1,-1);
low.resize(n+1);
DF(1,0,0);
g<<C.size()<<'\n';
for(size_t i=0; i<C.size(); i++)
{
sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
for(size_t j=0; j<C[i].size(); j++)
g<<C[i][j]<<" ";
g<<'\n';
}
return 0;
}