Pagini recente » Cod sursa (job #2673190) | Cod sursa (job #1206069) | Clasament teme_acmunibuc_2013 | Cod sursa (job #2757940) | Cod sursa (job #1273772)
#include <algorithm>
#include <fstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
vector<vector<int>> adj, comp;
vector<int> dfn, low;
vector<bool> vis;
stack<pair<int,int>> s;
void read()
{
ifstream fin("biconex.in");
int n, m;
fin >> n >> m;
adj.resize(n + 1);
dfn.resize(n + 1);
low.resize(n + 1);
vis.resize(n + 1);
fill(low.begin(), low.end(), (1 << 30));
for (int i = 0; i < m; ++i)
{
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
fin.close();
}
void write()
{
ofstream fout("biconex.out");
fout << comp.size() << '\n';
for (auto bc : comp)
{
for (auto i : bc)
fout << i << ' ';
fout << '\n';
}
fout.close();
}
//Component that starts with u
void add_component(pair<int, int> p)
{
vector<int> bc;
while (s.top() != p)
{
bc.push_back(s.top().second); bc.push_back(s.top().first);
s.pop();
}
//Add the p pair
bc.push_back(s.top().second); bc.push_back(s.top().first);
s.pop();
//Remove repeating nodes
bc.erase(unique(bc.begin(), bc.end()), bc.end());
sort(bc.begin(), bc.end());
comp.push_back(bc);
}
void dfs(int u, int parent, int lvl)
{
vis[u] = true;
dfn[u] = lvl;
low[u] = lvl;
for (int v : adj[u])
{
if (v == parent)
continue;
if (vis[v] == false)
{
s.push(make_pair(u, v));
dfs(v, u, 1 + dfn[u]);
if (low[v] >= dfn[u])
add_component(make_pair(u, v));
}
low[u] = min(low[u], low[v]);
}
}
int main()
{
read();
dfs(1, -1, 0);
write();
return 0;
}