Pagini recente » Cod sursa (job #3199870) | Cod sursa (job #2030349) | Cod sursa (job #2840520) | Cod sursa (job #1040449) | Cod sursa (job #2534946)
#include <fstream>
#include<vector>
#include<algorithm>
#include <iostream>
using namespace std;
ofstream fout("biconex.out");
ifstream fin("biconex.in");
struct muchie
{
int fiu, tata;
};
muchie S[200005];
vector<int>a[200005];
vector<vector <int> >bi;
int ord[200005],lowLink[200005],cate,nrOrd,varf;
int n,m;
void citire()
{
int k,x,y;
fin>>n>>m;
for(k=1;k<=m;k++)
{
fin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void dfs(int nodCurr, int nodTata)
{
int i,nod,x,y;
muchie h;
nrOrd++;
ord[nodCurr]=lowLink[nodCurr]=nrOrd;
for(i=0;i<a[nodCurr].size();i++)
{
nod=a[nodCurr][i];
if(ord[nod]==-1)
{
varf++;
S[varf].tata=nodCurr;
S[varf].fiu=nod;
dfs(nod,nodCurr);
lowLink[nodCurr]=min(lowLink[nodCurr],lowLink[nod]);
if(lowLink[nod]==ord[nodCurr])
{
cate++;
vector<int>aux;
while(y!=nodCurr || x!=nod)
{
x=S[varf].fiu;
y=S[varf].tata;
varf--;
aux.push_back(x);
aux.push_back(y);
}
bi.push_back(aux);
}
}
else
lowLink[nodCurr]=min(lowLink[nodCurr],ord[nod]);
}
}
int main()
{
citire();
int i,j;
for(i=1;i<=n;i++)
ord[i]=lowLink[i]=-1;
S[0].fiu=1;
S[0].tata=-1;
dfs(1,0);
fout<<cate<<"\n";
for(i=0;i<bi.size();i++)
{
sort(bi[i].begin(), bi[i].end());
bi[i].erase(unique(bi[i].begin(), bi[i].end()), bi[i].end());
for(j=0;j<bi[i].size();j++)
fout<<bi[i][j]<<" ";
fout<<"\n";
}
return 0;
}