Pagini recente » Cod sursa (job #297953) | Cod sursa (job #2356679) | Cod sursa (job #2203498) | Rating Viman Andrei (VimanA) | Cod sursa (job #1948874)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 100005
#define vertex 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,Depth[MaxN],Sort[MaxN],Size=0,Stack[MaxN],Index[MaxN],depth=0,Col[MaxN];
bool found[MaxN];
queue<int>Q;
vector<int> Graph[MaxN],Back[MaxN],Out[MaxN];
vector<pair<int,int> >T[MaxN];
void Topological_Sort(int vertex)
{
bool stop=false;
depth=0;
Stack[++depth]=vertex;
Index[depth]=0;
while(depth)
{
vertex=Stack[depth];
if(Index[depth]==0)
found[vertex]=true;
stop=false;
for(int i=Index[depth];i<T[vertex].size();i++)
{
Index[depth]++;
if(!found[T[vertex][i].vertex])
{
Stack[++depth]=T[vertex][i].vertex;
stop=true;
Index[depth]=0;
break;
}
}
if(!stop)
Sort[++Size]=Stack[depth],depth--;
}
}
void Get_Back(int vertex,int father)
{
Stack[++depth]=vertex;
Index[depth]=0;
bool stop=false;
while(depth)
{
vertex=Stack[depth];
father=Stack[depth-1];
if(Index[depth]==0)
{
Depth[vertex]=depth;
found[vertex]=true;
Father[vertex]=father;
Low[vertex]=vertex;
}
stop=false;
for(int i=Index[depth];i<Graph[vertex].size();i++)
{
Index[depth]++;
if(!found[Graph[vertex][i]])
{
T[vertex].push_back(make_pair(Graph[vertex][i],-1));
Stack[++depth]=Graph[vertex][i];
stop=true;
Index[depth]=0;
break;
}
else if(Depth[vertex]+1<Depth[Graph[vertex][i]])
Back[vertex].push_back(Graph[vertex][i]);
}
if(!stop)
depth--;
}
}
void Get_Low(int vertex)
{
int L=Low[vertex];
for(int i=0;i<Back[vertex].size();i++)
if(Low[Back[vertex][i]]!=L)Q.push(Back[vertex][i]);
while(!Q.empty())
{
if(Low[Q.front()]!=L)
Low[Q.front()]=L,Q.push(Father[Q.front()]);
Q.pop();
}
}
void Mark_Edges(int vertex,int C)
{
bool stop=false;
depth=0;
Stack[++depth]=vertex;
Index[depth]=0;
while(depth)
{
vertex=Stack[depth];
C=Col[depth];
stop=false;
for(int i=Index[depth];i<T[vertex].size();i++)
{
Index[depth]++;
if(Low[T[vertex][i].vertex]==Low[Father[vertex]])
{
T[vertex][i].colour=C;
Stack[++depth]=T[vertex][i].vertex;
Index[depth]=0;
Col[depth]=C;
stop=true;
break;
}
else
{
T[vertex][i].colour=++Colour;
Stack[++depth]=T[vertex][i].vertex;
Index[depth]=0;
Col[depth]=Colour;
stop=true;
break;
}
}
if(!stop)
depth--;
}
}
void Get_Comp(int vertex,int C)
{
bool stop=false;
depth=0;
Stack[++depth]=vertex;
Index[depth]=0;
while(depth)
{
vertex=Stack[depth];
if(Index[depth]==0)
Out[Comp].push_back(vertex);
stop=false;
for(int i=Index[depth];i<T[vertex].size();i++)
{
Index[depth]++;
if(T[vertex][i].colour==C)
{
Stack[++depth]=T[vertex][i].vertex;
Index[depth]=0;
stop=true;
break;
}
}
if(!stop)
depth--;
}
}
void Get_BCC(int vertex)
{
for(int i=0;i<T[vertex].size();i++)
if(!found[T[vertex][i].colour])
{
found[T[vertex][i].colour]=true;
Out[++Comp].push_back(vertex);
Get_Comp(T[vertex][i].vertex,T[vertex][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);
memset(found,0,sizeof found);
Topological_Sort(1);
for(int i=N;i>0;i--)
Get_Low(Sort[i]);
Mark_Edges(1,0);
memset(found,0,sizeof found);
for(int i=N;i>0;i--)
Get_BCC(Sort[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;
}