Pagini recente » Cod sursa (job #163903) | Cod sursa (job #174652) | Cod sursa (job #322995) | Cod sursa (job #2676262) | Cod sursa (job #484401)
Cod sursa(job #484401)
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstring>
//#include"verificator.cpp"
#define pb push_back
struct much{
int n1,n2;};
ofstream fout("biconex.out");
int t[100005],niv[100005],low[100005],N,M,toleranta;
vector<int> G[100005];
vector<vector<int> > sol;
stack<much> S;
void cit();
void extrage(int x,int y)
{ vector<int> con;
much dummy;
do
{dummy=S.top();
S.pop();
//cout<<dummy.n1<<" "<<dummy.n2<<" ";
con.pb(dummy.n1);
con.pb(dummy.n2);
}
while(dummy.n1!=x||dummy.n2!=y);
sol.pb(con);
}
int lev=0;
void dfs(int v,int tata)
{vector<int>::iterator it;
int w;
niv[v]=++lev;
low[v]=lev;
t[v]=tata;
for(it=G[v].begin();it!=G[v].end();it++)
{ w=*it;
if(tata!=w&&(niv[w]<niv[v]))
{
S.push((much){v,w});
}
if(niv[w]==0)
{ //S.push((much){v,w});
dfs(w,v);
low[v]=min(low[v],low[w]);
if(niv[v]<=low[w])
{ toleranta++;
//cout<<"\n";
extrage(v,w);
}
}
else
low[v]=min(low[v],niv[w]);
}
}
char a[100000],b[100000];
/*void main1()
{int i=1,ok=1;
ifstream fin("biconex1.out");
ifstream fin1("grader_test5.ok");
do
{ fin.getline(a,10000);
fin1.getline(b,10000);
if(strcmp(a,b)==0)
i++;
else
ok=0;
}
while(ok);
cout<<i<<" ";
}*/
int main()
{int i,mos=-1;;
vector<int>::iterator it;
cit();
dfs(1,0);
fout<<sol.size()<<"\n";
for(i=0;i<sol.size();i++)
{sort(sol[i].begin(),sol[i].end());
mos=-1;
for(it=sol[i].begin();it!=sol[i].end();it++)
if(*it!=mos)
{
mos=*it;
fout<<*it<<" ";
}
fout<<"\n";
}
//main1();
fout.close();
return 0;
}
void cit()
{
int i,x,y;
ifstream fin("biconex.in");
fin>>N>>M;
for(i=1;i<=M;i++)
{
fin>>x>>y;
G[x].pb(y);
G[y].pb(x);
//cout<<G[x].back()<<" "<<G[y].back()<<"\n";
}
fin.close();
}