Pagini recente » Cod sursa (job #11841) | Statistici Mihalache Giorgian catalin (Gica47) | Cod sursa (job #2471684) | Monitorul de evaluare | Cod sursa (job #1528375)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
std::vector < std::vector < int > > adj_m;
std::vector < int > dis, low;
std::vector < std::vector < int > > comps;
std::stack < std::pair < int , int > > st;
void stack_it(int na, int nb)
{
std::vector < int > comp;
int x, y;
do
{
x = st.top().first;
y = st.top().second;
st.pop();
comp.push_back(x);
comp.push_back(y);
}while(x != na || y != nb);
comps.push_back(comp);
}
void dfs(int node, int father, int time)
{
dis [node] = low [node] = time;
std::size_t i;
for(i = 1 ; i < adj_m[node].size() ; ++i)
{
int cnode = adj_m[node][i];
if(cnode == father)
continue;
if(dis[cnode] == -1)
{
st.push(std::make_pair(node, cnode));
dfs(cnode, node, time + 1);
low[node] = std::min(low[node], low[cnode]);
if(low[cnode] >= dis[node])
{
stack_it(node, cnode);
}
}
else
{
low[node] = std::min(low[node], dis[cnode]);
}
}
}
int main()
{
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int n, m;
fin >> n;
adj_m.assign(n + 1, std::vector < int >(1));
dis.assign(n + 1, -1);
low.assign(n + 1, 0);
fin >> m;
int c;
int na, nb;
for(c = 1 ; c <= m ; ++c)
{
fin >> na >> nb;
adj_m[na].push_back(nb);
adj_m[nb].push_back(na);
}
dfs(1, 0, 1);
fout << comps.size() << "\n";
std::size_t i, j;
for(i = 0 ; i < comps.size(); ++i)
{
std::sort(comps[i].begin(), comps[i].end());
comps[i].erase(std::unique(comps[i].begin(), comps[i].end()), comps[i].end());
for(j = 0 ; j < comps[i].size() ; ++j)
{
fout << comps[i][j] << " ";
}
fout << "\n";
}
return 0;
}