Pagini recente » Cod sursa (job #653718) | Cod sursa (job #2734109) | Cod sursa (job #2027790) | Cod sursa (job #1610516) | Cod sursa (job #994364)
Cod sursa(job #994364)
#include <algorithm>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#define FOR(i,a,b) for( int i = (a) ; i <= (b); ++i)
#define Nmax 100005
#define Mmax 200005
#define pb push_back
using namespace std;
vector< int > lv[Nmax],sol[Nmax];
bitset< Nmax > used;
stack<pair<int,int> > s;
int niv[ Nmax ],tata[ Nmax ],artic[ Nmax ], nmin[ Nmax ];
int N,M,fr,x,y,i,ncc=0;
void get_graph()
{
scanf("%d %d",&N,&M);
int a,b;
FOR(i,1,M){
scanf("%d %d",&a,&b);
lv[ a ].push_back(b);
lv[ b ].push_back(a);
}
}
void DFS ( int nodc ){
used[ nodc ] = true;
nmin[ nodc ] = niv[ nodc ];
for(vector<int> ::iterator it = lv[ nodc ].begin(); it != lv[ nodc ].end(); ++it)
if(used[*it] == false){
s.push(make_pair(nodc,*it));
niv[ *it ] = niv[ nodc ]+1;
if(nodc == 1) ++fr;
tata[ *it ] = nodc;
DFS(*it);
if(nmin[ *it ] < nmin[ nodc ])
nmin[ nodc ]=nmin[ *it ];
if(nmin[ *it ] >= niv[ nodc ])
{
artic[ nodc ] = 1;
++ncc;
x=s.top().first;
y=s.top().second;
s.pop();
sol[ncc].pb(x);sol[ncc].pb(y);
while(x!=nodc || y!=*it)
{
x=s.top().first;
y=s.top().second;
s.pop();
sol[ncc].pb(x);
}
}
}
else if(tata[ nodc ] != *it && nmin[ *it ] < niv [ nodc ])
nmin[ nodc ]= niv [ *it ];
}
int j;
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
get_graph();
niv[ 1 ]=1;
DFS(1);
if(fr<=1)artic[1]=0;
printf("%d\n",ncc);
for(i=1;i<=ncc;i++)
{
for(j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}