Pagini recente » Cod sursa (job #1758254) | Cod sursa (job #3001549) | Cod sursa (job #865593) | Cod sursa (job #2022916) | Cod sursa (job #1380241)
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <bitset>
#include <algorithm>
const int MAX_N(100001);
int n, Bc, Level [MAX_N], LowLevel [MAX_N];
std::vector<int> Graph [MAX_N], Components [MAX_N];
std::stack<std::pair<int,int>> Stack;
std::bitset<MAX_N> Mark;
inline void Read (void)
{
std::ifstream input("biconex.in");
int m;
input >> n >> m;
int x, y;
while (m)
{
input >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
--m;
}
input.close();
}
inline void Print (void)
{
std::ofstream output("biconex.out");
output << Bc << '\n';
for (int i(1) ; i <= Bc ; ++i)
{
for (unsigned int j(0) ; j < Components[i].size() ; ++j)
output << Components[i][j] << ' ';
output.put('\n');
}
output.close();
}
void GetComponent (std::pair<int,int> e)
{
std::vector<int> c;
Mark.reset();
while (Stack.top() != e)
{
if (!Mark[Stack.top().first])
{
c.push_back(Stack.top().first);
Mark[Stack.top().first] = true;
}
if (!Mark[Stack.top().second])
{
c.push_back(Stack.top().second);
Mark[Stack.top().second] = true;
}
Stack.pop();
}
if (!Mark[e.first])
{
c.push_back(e.first);
Mark[e.first] = true;
}
if (!Mark[e.second])
{
c.push_back(e.second);
Mark[e.second] = true;
}
Stack.pop();
++Bc;
Components[Bc] = c;
}
void BiconnectedComponents (int node, int parent, int depth)
{
Level[node] = LowLevel[node] = depth;
for (unsigned int i(0) ; i < Graph[node].size() ; ++i)
if (Graph[node][i] == parent)
continue;
else if (Level[Graph[node][i]])
LowLevel[node] = std::min(LowLevel[node],Level[Graph[node][i]]);
else
{
Stack.push(std::make_pair(node,Graph[node][i]));
BiconnectedComponents(Graph[node][i],node,depth + 1);
LowLevel[node] = std::min(LowLevel[node],LowLevel[Graph[node][i]]);
if (LowLevel[Graph[node][i]] >= Level[node])
GetComponent(std::make_pair(node,Graph[node][i]));
}
}
int main (void)
{
Read();
for (int i(1) ; i <= n ; ++i)
if (!Level[i])
BiconnectedComponents(i,i,1);
Print();
return 0;
}