Pagini recente » Cod sursa (job #2555521) | Cod sursa (job #2923449) | Cod sursa (job #14673) | Cod sursa (job #2625456) | Cod sursa (job #2359503)
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=10000;
vector <int>G[NMAX+5];
vector <int>dfs_discover, dfs_low, articulation_vertex, dfs_parent;
set <int>componente_biconexe[NMAX+5];
set <int>::iterator it;
struct muchie
{
int nod1, nod2;
};
muchie st[NMAX+5];
int top;
int timp, dfsRoot, rootChildren, n, nr;
void articulationPoint(int u)
{
int v, j;
muchie aux;
timp++;
dfs_discover[u]=dfs_low[u]=timp;
for(j=0;j<G[u].size();j++)
{
v=G[u][j];
if(!dfs_discover[v])
{
///formez componenta biconexa
aux.nod1=u;
aux.nod2=v;
st[++top]=aux;
dfs_parent[u]=v;
if(u==dfsRoot)
rootChildren++;
articulationPoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=1;
///bag in solutie componenta biconexa;
nr++;
while(top>0)
{
componente_biconexe[nr].insert(st[top].nod1);
componente_biconexe[nr].insert(st[top].nod2);
top--;
}
}
dfs_low[u]=min(dfs_low[u], dfs_low[v]);
}
else
{
if(dfs_parent[u]!=v)
dfs_low[u]=min(dfs_low[u], dfs_discover[v]);
}
}
}
int main()
{
int m, u, v, i;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs_parent.assign(n+1, 0);
dfs_low.assign(n+1, 0);
dfs_discover.assign(n+1, 0);
articulation_vertex.assign(n+1, 0);
for(i=1;i<=n;i++)
{
if(dfs_discover[i]==0)
{
dfsRoot=i;
rootChildren=0;
articulationPoint(i);
articulation_vertex[dfsRoot]=(rootChildren>1);
}
}
fout<<nr<<"\n";
for(i=1;i<=nr;i++)
{
for(it=componente_biconexe[i].begin();it!=componente_biconexe[i].end();it++)
fout<<(*it)<<" ";
fout<<"\n";
}
return 0;
}