Pagini recente » Cod sursa (job #200422) | Cod sursa (job #3126640) | Cod sursa (job #2057508) | Cod sursa (job #1683590) | Cod sursa (job #2672076)
#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 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[nodeIndex])
{
if(neighbor.indexProcessed == -1)
{
stk.push(make_pair(nodeIndex, neighborIndex));
FindArticulationPoints(neighborIndex, nextAvailableIndex);
node.lowlink = min(neighbor.lowlink, node.lowlink);
if(neighbor.lowlink >= node.indexProcessed)
{
GenerateBiconexComponent(nodeIndex);
}
}
else
{
node.lowlink = min(neighbor.indexProcessed, node.lowlink);
}
}
}
int main()
{
int n, m;
fin >> n >> m;
graphVertexes.resize(n + 1);
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;
}