Pagini recente » Cod sursa (job #3208674) | Cod sursa (job #2801678) | Cod sursa (job #2260632) | Cod sursa (job #1574045) | Cod sursa (job #2681699)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
const int NMAX = 100000;
std::vector<int>g[NMAX + 3];
std::vector<int>discover,low,articulation,parent;
std::stack<std::pair<int,int>>st;
std::vector<int>sol[NMAX];
int timp,root,children,sols;
void dfs(int u)
{
int v;
timp++;
discover[u] = low[u] = timp;
for(int i = 0;i < g[u].size();i++)
{
v = g[u][i];
if(!discover[v])
{
st.push({u,v});
parent[v] = u;
if(u == root)
children++;
dfs(v);
if(low[v] >= discover[u])
{
sols++;
std::pair<int,int>aux = st.top();
do
{
sol[sols].push_back(st.top().second);
aux = st.top();
st.pop();
}while(!(st.empty() || aux.first == u || aux.second == v));
sol[sols].push_back(aux.first);
articulation[u] = 1;
}
low[u] = std::min(low[u],low[v]);
}
else if(v != parent[u])
low[u] = std::min(low[u],discover[v]);
}
}
int main()
{
int n,m,u,v;
in>>n>>m;
for(int i = 1;i <= m;i++)
{
in>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
discover.assign(n+1,0);
low.assign(n+1,0);
articulation.assign(n+1,0);
parent.assign(n+1,0);
for(int i = 1;i <= n;i++)
{
if(!discover[i])
{
sols = 0;
root = i;
children = 0;
dfs(i);
articulation[root] = (children>1);
}
}
out<<sols<<'\n';
for(int i = 1;i <= sols;i++)
{
for(int j = 0;j < sol[i].size();j++)
out<<sol[i][j]<<' ';
out<<'\n';
}
return 0;
}