Pagini recente » Cod sursa (job #1467859) | Cod sursa (job #1392286) | Cod sursa (job #2335687) | Cod sursa (job #2320787) | Cod sursa (job #3263483)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, x, y, timer;
vector<vector<int>> graf;
vector<int> tin, low, viz;
stack<pair<int, int>> s;
vector<set<int>> comp;
void bicon(int node1, int node2)
{
set<int> bic;
int tn1 = -1, tn2 = -1;
while(tn1 != node1 || tn2 != node2)
{
tn1 = s.top().first;
tn2 = s.top().second;
s.pop();
bic.insert(tn1);
bic.insert(tn2);
}
comp.push_back(bic);
}
void dfs(int node, int parent)
{
viz[node] = 1;
low[node] = tin[node] = ++timer;
for(auto next:graf[node])
{
if(next == parent)
continue;
if(viz[next])
low[node] = min(low[node], tin[next]);
else
if(!viz[next])
{
s.push({node, next});
dfs(next, node);
low[node] = min(low[node], low[next]);
if(low[next] >= tin[node]) //pct de art
bicon(node, next);
}
}
}
int main()
{
cin >> n >> m;
graf.assign(n+1, vector<int>());
viz.resize(n+1);
tin.resize(n+1);
low.resize(n+1);
for(int i=1; i<=m; i++)
{
cin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!viz[i])
dfs(i, 0);
cout << comp.size() << '\n';
for(int i=0; i<comp.size(); i++, cout << '\n')
{
for(auto node:comp[i])
cout << node << " ";
}
return 0;
}