Pagini recente » Cod sursa (job #2834886) | Cod sursa (job #2248311) | Cod sursa (job #572683) | Cod sursa (job #2654911) | Cod sursa (job #1735788)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstdio>
#include <algorithm>
using namespace std;
vector<vector<int> > graph;
int n,m;
vector<int> idx;
vector<int> lowlink;
stack<pair<int,int> > s;
vector<vector<int> > bc;
void store_bc(int x1, int x2)
{
int n1, n2;
bc.resize(bc.size()+1);
do {
//if (s.empty())
// break;
n1 = s.top().first;
n2 = s.top().second;
s.pop();
bc[bc.size()-1].push_back(n1);
bc[bc.size()-1].push_back(n2);
} while (n1 != x1 || n2 != x2);
}
//num nu trebuie sa creasca non-stop, deoarece nu-mi foloseste
//la determinarea CB, cum era la CTC
void dfs(int node, int prevNode, int num)
{
//cout<<node<<endl;
idx[node]=num;
lowlink[node] = num;
for (int i = 0; i < graph[node].size(); i++)
{
if (graph[node][i] == prevNode)
continue;
if (idx[graph[node][i]] == -1)
{
s.push(make_pair(node, graph[node][i]));
dfs(graph[node][i], node, num+1);
lowlink[node] = min (lowlink[node], lowlink[graph[node][i]]);
//daca e punct de articulatie
if (lowlink[graph[node][i]] >= idx[node])
{
store_bc(node, graph[node][i]);
}
}
else
{
lowlink[node] = min (lowlink[node], idx[graph[node][i]]);
}
}
}
int main()
{
int x,y;
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
graph.resize(n+1);
idx.resize(n+1, -1);
lowlink.resize(n+1, -1);
for (int i = 1; i <= m; i++)
{
scanf ("%d %d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
dfs(1,0,0);
cout<<bc.size()<<"\n";
for (int i = 0; i < bc.size();i++)
{
sort(bc[i].begin(), bc[i].end());
bc[i].erase(unique(bc[i].begin(), bc[i].end()), bc[i].end());
for (int j = 0 ; j < bc[i].size(); j++)
{
cout<<bc[i][j]<<" ";
}
cout<<"\n";
}
}