Pagini recente » Cod sursa (job #279815) | Cod sursa (job #2958825) | Cod sursa (job #271669) | Cod sursa (job #2861152) | Cod sursa (job #2672066)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define node graphVertexes[nodeIndex]
#define neighbor graphVertexes[neighborIndex]
#define nextAvailableIndex availableIndex + 1
const int N_MAX = 1e5 + 1;
struct ReindexedVertex{
int index, indexProcessed = -1, lowlink;
};
vector <int> graph[N_MAX];
vector <ReindexedVertex> graphVertexes;
vector <set <int>> solutions;
stack <pair <int, int>> stk;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void GenerateBiconexComponent(int parentIndex)
{
set<int> sol;
int st, dr;
while(st != parentIndex)
{
st = stk.top().first;
dr = stk.top().second;
stk.pop();
sol.insert(st);
sol.insert(dr);
}
solutions.push_back(sol);
}
void FindArticulationPoints(int nodeIndex, int availableIndex)
{
node.indexProcessed = availableIndex;
node.lowlink = availableIndex;
for(auto neighborIndex: graph[node.index])
{
if(neighbor.indexProcessed == -1)
{
stk.push(make_pair(nodeIndex, neighbor.index));
FindArticulationPoints(neighbor.index, nextAvailableIndex);
node.lowlink = min(neighbor.lowlink, node.lowlink);
if(neighbor.lowlink >= node.indexProcessed)
{
GenerateBiconexComponent(node.index);
}
}
else if(neighbor.indexProcessed != -1)
{
node.lowlink = min(neighbor.indexProcessed, node.lowlink);
}
}
}
int main()
{
int n, m;
fin >> n >> m;
graphVertexes.resize(n + 1);
for(int i = 1; i <= n; i++)
{
graphVertexes[i].index = i;
}
for(int i = 0, st, dr; i < m; i++)
{
fin >> st >> dr;
graph[st].push_back(dr);
graph[dr].push_back(st);
}
FindArticulationPoints(1, 1);
fout << solutions.size() << '\n';
for(auto sol: solutions)
{
for(auto val: sol)
{
fout << val << ' ';
}
fout << '\n';
}
return 0;
}