Pagini recente » Cod sursa (job #1669186) | Cod sursa (job #3198365) | Cod sursa (job #1599330) | Cod sursa (job #1126351) | Cod sursa (job #1157228)
#include <iostream>
#include <fstream>
#include <vector>
#define max 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,nr_comp;
int cicluri[max],viz[max];//Lung_ciclu[100];
vector <int> v[max];
vector <int> c;
vector <int> comp[max];
int cicluri_complet ()
{
for (int i=1; i<=n; i++)
if (cicluri[i]==0)
return 0;
return 1;
}
int viz_complet ()
{
for (int i=1; i<=n; i++)
if (viz[i]==0)
return 0;
return 1;
}
int exista_muchie_c ( int x )
{
for (int i=0; i<v[x].size(); i++)
if (cicluri[v[x][i]]==0)
return v[x][i];
return 0;
}
int exista_muchie_v ( int x )
{
for (int i=0; i<v[x].size(); i++)
if (viz[v[x][i]]==0)
return v[x][i];
return 0;
}
int inchide_ciclu ( int x )
{
int i,j;
for ( i=0; i<c.size()-2; i++ )
for ( j=0; j<v[x].size(); j++ )
if ( c[i]==v[x][j] )
return i;
return -1;
}
int calc_nr_comp()
{
for (int i=0; i<10000; i++)
if (comp[i].size()==0)
return i;
}
void completare_cicluri(int x)
{
int k=0,i,j;
cicluri[x]=x;
c.push_back (x);
while ( !cicluri_complet () )
{
i=exista_muchie_c (c[k]); //returneaza nodul
if (i)
{
c.push_back (i);
k++;
cicluri[c[k]]=c[k];
if (k>=2)
{
int p=inchide_ciclu (c[k]); //returneaza pozitia inchizatorului in c
if (p!=-1)
{
j=c.size()-1;
while (cicluri[c[j]]!=cicluri[c[p]])
{
cicluri[c[j]]=cicluri[c[p]];
j--;
}
}
}
}
else
{
while (!i)
{
c.pop_back();
k--;
i=exista_muchie_c (c[k]);
}
}
}
c.clear();
}
void prelucrare(int start, int x)
{
int i,ok=0;
for (i=start; i<x; i++)
if (cicluri[c[i]]==cicluri[c[i+1]])
{
/*int t=i;
while (t<x && cicluri[c[t]]==cicluri[c[t+1]])
t++;
if (Lung_ciclu[c[i]]==t-i)
{*/
nr_comp=calc_nr_comp();
while (i<x && cicluri[c[i]]==cicluri[c[i+1]])
{
comp[nr_comp].push_back(c[i]);
i++;
}
comp[nr_comp].push_back(c[i]);
i--;
}
else
{
nr_comp=calc_nr_comp();
comp[nr_comp].push_back(c[i]);
comp[nr_comp].push_back(c[i+1]);
}
}
void biconex(int x)
{
completare_cicluri(x);
int k=0,i,j,initial=0;
viz[x]=1;
c.push_back (x);
while ( !viz_complet() )
{
i=exista_muchie_v (c[k]); //returneaza nodul
if (i)
{
c.push_back (i);
k++;
viz[c[k]]=1;
}
else
{
prelucrare(initial,k);
while (!i)
{
c.pop_back();
k--;
i=exista_muchie_v (c[k]);
}
initial=k;
}
}
prelucrare(initial,c.size()-1);
c.clear();
}
int main()
{
int x,y,i,j; // n=nr noduri
f>>n;
f>>m;
for (i=0; i<m; i++)
{
f>>x;
f>>y;
v[x].push_back(y);
v[y].push_back(x);
}
biconex(1);
for (i=0; i<n; i++)
if (comp[i].size()==0)
{
nr_comp=i;
break;
}
g<<nr_comp<<'\n';
for (i=0; i<nr_comp; i++)
{
for (j=0; j<comp[i].size(); j++)
g<<comp[i][j]<<" ";
g<<'\n';
}
return 0;
}