Pagini recente » Cod sursa (job #1234450) | Cod sursa (job #1009720) | Cod sursa (job #2799091) | Cod sursa (job #1668151) | Cod sursa (job #838136)
Cod sursa(job #838136)
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
typedef vector<int>::iterator it;
FILE *f = fopen("biconex.in","r");
FILE *g = fopen("biconex.out","w");
#define MaxN 100100
int N,M,Sol;
int viz[MaxN],stiva[MaxN];
vector<int> A[MaxN];
queue<int> SolV[MaxN];
void citire(void)
{
int a,b;
fscanf(f,"%d %d",&N,&M);
for(int i=1;i<=M;i++)
{
fscanf(f,"%d %d",&a,&b);
A[a].push_back(b);
A[b].push_back(a);
}
}
inline void adaugaComp(int a)
{
++ Sol;
for(int i=a;stiva[i];++i)
SolV[Sol].push(stiva[i]),
i!=a ? stiva[i] = 0 : 0;
}
inline int min(int a,int b)
{
return a < b ? a : b;
}
inline int compBiconexe(int a)
{
int Min1 = viz[a]-1,Min2,nr = 0;
stiva[viz[a]] = a;
for(it i=A[a].begin();i<A[a].end();i++)
if(!viz[*i])
{
viz[*i] = viz[a]+1;
Min2 = compBiconexe(*i);
if(Min2 >= viz[a])
adaugaComp(viz[a]);
Min1 = min(Min1,Min2);
++ nr;
}
else
Min1 = min(Min1,viz[*i]);
if(viz[a] == 1 && nr >= 2 && stiva[2])
adaugaComp(1);
return Min1;
}
void Rezolvare(void)
{
for(int i=1;i<=N;i++)
if(!viz[i])
{
viz[i] = 1;
compBiconexe(i);
}
//for(int i=1;i<=N;i++)
// printf("%d ",viz[i]);
}
int main()
{
citire();
Rezolvare();
fprintf(g,"%d\n",Sol);
for(int i=1;i<=Sol;i++,fprintf(g,"\n"))
for(;!SolV[i].empty();SolV[i].pop())
fprintf(g,"%d ",SolV[i].front());
}