Pagini recente » Cod sursa (job #2257227) | Cod sursa (job #1983903) | Cod sursa (job #2869923) | Cod sursa (job #2111897) | Cod sursa (job #1948710)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 1005
#define node first
#define colour second
#define INF 2140000000
using namespace std;
FILE*IN,*OUT;
int N,M,X,Y,Father[MaxN],Low[MaxN],Cnt=0,Colour=0,Comp=0;
bool found[MaxN];
queue<int>Q;
vector<int> Graph[MaxN],Back[MaxN],Out[MaxN];
vector<pair<int,int> >T[MaxN];
void Get_Back(int node,int father)
{
found[node]=true;
Father[node]=father;
Low[node]=node;
for(int i=0;i<Graph[node].size();i++)
{
if(!found[Graph[node][i]])
Get_Back(Graph[node][i],node),T[node].push_back(make_pair(Graph[node][i],-1));
else if(Graph[node][i]!=Father[node])Back[node].push_back(Graph[node][i]);
}
}
void Get_Low(int node)
{
int L=Low[node];
for(int i=0;i<Back[node].size();i++)
if(Low[Back[node][i]]!=L)Q.push(Back[node][i]);
while(!Q.empty())
{
if(Low[Q.front()]!=L)
Low[Q.front()]=L,Q.push(Father[Q.front()]);
Q.pop();
}
}
void Mark_Edges(int node,int C)
{
for(int i=0;i<T[node].size();i++)
{
if(Low[T[node][i].node]==Low[Father[node]])
{
T[node][i].colour=C;
Mark_Edges(T[node][i].node,C);
}
else
{
T[node][i].colour=++Colour;
Mark_Edges(T[node][i].node,Colour);
}
}
}
void Get_Comp(int node,int C)
{
Out[Comp].push_back(node);
for(int i=0;i<T[node].size();i++)
if(T[node][i].colour==C)
Get_Comp(T[node][i].node,C);
}
void Get_BCC(int node)
{
for(int i=0;i<T[node].size();i++)
if(!found[T[node][i].colour])
{
found[T[node][i].colour]=true;
Out[++Comp].push_back(node);
Get_Comp(T[node][i].node,T[node][i].colour);
}
}
int main()
{
IN=fopen("biconex.in","r");
OUT=fopen("biconex.out","w");
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);
}
Get_Back(1,0);
for(int i=1;i<=N;i++)
Get_Low(i);
Mark_Edges(1,0);
memset(found,0,sizeof found);
for(int i=1;i<=N;i++)
Get_BCC(i);
fprintf(OUT,"%d\n",Comp);
for(int i=1;i<=Comp;i++)
{
for(int j=0;j<Out[i].size();j++)
fprintf(OUT,"%d ",Out[i][j]);
fprintf(OUT,"\n");
}
return 0;
}