Pagini recente » Cod sursa (job #1971550) | Cod sursa (job #552008) | Cod sursa (job #397555) | Cod sursa (job #2291859) | Cod sursa (job #475522)
Cod sursa(job #475522)
// Componente biconexe.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include "stdio.h"
#include <vector>
#include <algorithm>
using namespace std;
FILE *f=fopen("biconex.in", "r");
FILE *g=fopen("biconex.out", "w");
typedef struct nod
{
int x;
struct nod *adr;
};
nod *l[100001];
int n, m, nr;
int dfn[100001], low[100001];
int cds[100001];
int cdf[100001];
int st;
int cv;
vector < vector<int> > c;
void add(int x, int y)
{
nod *p=new nod;
p->x=y;
p->adr=l[x];
l[x]=p;
}
void read()
{
fscanf(f, "%d%d", &n, &m);
for (int i=1; i<=m; ++i)
{
int x, y;
fscanf(f, "%d%d", &x, &y);
add(x, y);
add(y, x);
}
}
void init()
{
for (int i=1; i<=n; ++i)
dfn[i]=low[i]=-1;
cds[1]=-1;
cdf[1]=1;
}
int minim(int x, int y)
{
if (x<y) return x;
return y;
}
void afisare(int x, int u)
{
vector <int> con;
do
{
con.push_back(cds[st]);
con.push_back(cdf[st--]);
}while (cds[st+1]!=u || cdf[st+1]!=x);
cv++;
c.push_back(con);
}
void biconex (int u, int tu)
{
int x;
dfn[u]=low[u]=++nr;
nod *p=l[u];
while (p!=NULL)
{
x=p->x;
if (x!=tu && dfn[x]<dfn[u])
{
cds[++st]=u;
cdf[st]=x;
}
if (dfn[x]==-1)
{
biconex(x, u);
low[u]=minim(low[u], low[x]);
if (low[x]>=dfn[u])
{
afisare(x, u);
}
}
else
{
if (x!=tu)
low[u]=minim(low[u], dfn[x]);
}
p=p->adr;
}
}
int main()
{
read();
init();
biconex(1, -1);
fprintf(g, "%d\n", cv);
for (size_t i=0; i<c.size(); ++i)
{
sort(c[i].begin(), c[i].end());
for (size_t j = 0; j < c[i].size(); ++ j)
{
if (j==0)
fprintf(g, "%d ", c[i][j]);
else
{
while (c[i][j]==c[i][j-1]) j++;
if (j<c[i].size()) fprintf(g, "%d ", c[i][j]);
}
}
fprintf(g, "\n");
}
return 0;
}