Pagini recente » Cod sursa (job #1240913) | Cod sursa (job #2859074) | Cod sursa (job #968207) | Cod sursa (job #1919169) | Cod sursa (job #2359917)
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=100000;
vector <int>G[NMAX+5];
vector <int>dfs_discover, dfs_low, dfs_parent;
set<int>componente_biconexe[NMAX+5];
set<int>::iterator it;
struct muchie
{
int nod1, nod2;
};
stack <muchie>st;
int timp, n, nr;
void componenta(int x, int y)
{
int i, j;
nr++;
do
{
i=st.top().nod1;
j=st.top().nod2;
st.pop();
componente_biconexe[nr].insert(j);
componente_biconexe[nr].insert(i);
}while(i!=x or j!=y);
}
void DFS(int nod)
{
int fiu, j;
muchie aux;
timp++;
dfs_discover[nod]=dfs_low[nod]=timp;
for(j=0;j<G[nod].size();j++)
{
fiu=G[nod][j];
if(dfs_parent[fiu]!=nod)
{
if(!dfs_discover[fiu])
{
aux.nod1=nod;
aux.nod2=fiu;
st.push(aux);
dfs_parent[fiu]=nod;
DFS(fiu);
if(dfs_low[fiu]>=dfs_discover[nod])
{
///nod este punct de articulatie
///formez componenta biconexa
componenta(nod, fiu);
}
dfs_low[nod]=min(dfs_low[nod], dfs_low[fiu]);
}
else
dfs_low[nod]=min(dfs_low[nod], dfs_discover[fiu]);
}
}
}
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);
for(i=1;i<=n;i++)
{
if(dfs_discover[i]==0)
DFS(i);
}
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;
}