Pagini recente » Cod sursa (job #2463987) | Cod sursa (job #1607716) | Cod sursa (job #551038) | Cod sursa (job #1531857) | Cod sursa (job #2373952)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int>G[NMAX];
vector<int>dfs_discover,dfs_low,articulation_vertex,dfs_parent;
vector<vector<int> >rez;
stack<pair<int,int> >st;
int time,dfsRoot,rootChildren;
void smecher_sa_moara_mama(int u,int v)
{
vector<int>sol;
int x,y;
x=y=0;
do
{
x=st.top().first;
y=st.top().second;
sol.push_back(x);
sol.push_back(y);
st.pop();
}
while(x!=u || y!=v);
rez.push_back(sol);
}
void articulationPoint(int u)
{
int v,j;
time++;
dfs_discover[u]=dfs_low[u]=time;
for(j=0;j<G[u].size();++j)
{
v=G[u][j];
if(!dfs_discover[v])
{
dfs_parent[v]=u;
if(u==dfsRoot)
rootChildren++;
st.push(make_pair(u,v));
articulationPoint(v);
if(dfs_low[v]>=dfs_discover[u])
{
articulation_vertex[u]=1;
smecher_sa_moara_mama(u,v);
}
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 u,v,i,j,m,n;
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;
}
for(i=0;i<rez.size();++i)
{
sort(rez[i].begin(),rez[i].end());
for(j=0;j<rez[i].size();++j)
if(rez[i][j]!=rez[i][j-1])
fout<<rez[i][j]<<" ";
fout<<"\n";
}
return 0;
}