Pagini recente » Cod sursa (job #2445945) | Cod sursa (job #587968) | Cod sursa (job #885853) | Cod sursa (job #1731646) | Cod sursa (job #2106147)
#include <bits/stdc++.h>
#define INF 2140000000
#define MOD 1000000007
#define MaxN 100005
using namespace std;
FILE *IN=fopen("biconex.in","r"),*OUT=fopen("biconex.out","w");
vector <int> Graph[MaxN],junk;
int N,M,X,Y,L[MaxN],D[MaxN];
vector<pair<int,int> >Stack;
vector<vector<int> >Comp;
void WriteComponent(int node)
{
bool stop=0;
Comp.push_back(junk);
while(!stop)
{
if(node==Stack[Stack.size()-1].second)
stop=1;
Comp[Comp.size()-1].push_back(Stack[Stack.size()-1].first);
Stack.pop_back();
}
Comp[Comp.size()-1].push_back(node);
}
void DFS(int node,int father)
{
D[node]=L[node]=1+D[father];
for(int i=0;i<Graph[node].size();i++)
{
if(!D[Graph[node][i]])
{
Stack.push_back({Graph[node][i],node});
DFS(Graph[node][i],node);
L[node]=min(L[node],L[Graph[node][i]]);
if(L[Graph[node][i]]>=D[node])
WriteComponent(node);
}
else L[node]=min(L[node],D[Graph[node][i]]);
}
}
int main()
{
fscanf(IN,"%d %d",&N,&M);
for(int i=1;i<=M;i++)
{
fscanf(IN,"%d %d",&X,&Y);
Graph[X].push_back(Y);
Graph[Y].push_back(X);
}
for(int i=1;i<N;i++)
if(!D[i])DFS(i,0);
fprintf(OUT,"%d\n",Comp.size());
for(int i=0;i<Comp.size();i++)
{
for(int j=0;j<Comp[i].size();j++)
fprintf(OUT,"%d ",Comp[i][j]);
fprintf(OUT,"\n");
}
return 0;
}