Pagini recente » Cod sursa (job #2250442) | Cod sursa (job #3161185) | Cod sursa (job #2404383) | Cod sursa (job #55534) | Cod sursa (job #881178)
Cod sursa(job #881178)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
const int MAX_SIZE(100001);
int n, m;
std::vector<int> graph [MAX_SIZE];
std::stack<std::pair<int,int> > stack;
std::vector<std::vector<int> > components;
bool mark [MAX_SIZE];
int dfn [MAX_SIZE];
int low [MAX_SIZE];
inline int min (int a, int b)
{
return a < b ? a : b;
}
inline void read (void)
{
std::freopen("biconex.in","r",stdin);
std::scanf("%d %d",&n,&m);
int x, y;
for (int i(0) ; i < m ; ++i)
{
std::scanf("%d %d",&x,&y);
graph[x].push_back(y);
graph[y].push_back(x);
}
std::fclose(stdin);
}
inline void print (void)
{
std::freopen("biconex.out","w",stdout);
std::printf("%u\n",components.size());
unsigned int i, j;
for (i = 0 ; i < components.size() ; ++i)
{
for (j = 0 ; j < components[i].size() ; ++j)
std::printf("%d ",components[i][j]);
std::putchar('\n');
}
std::fclose(stdout);
}
void BiconnectedComponent (int x, int y)
{
std::vector<int> nodes;
int a, b;
do
{
a = stack.top().first;
b = stack.top().second;
if (!mark[a])
{
nodes.push_back(a);
mark[a] = true;
}
if (!mark[b])
{
nodes.push_back(b);
mark[b] = true;
}
stack.pop();
}
while (x != a && y != b);
for (unsigned int i(0), size(nodes.size()) ; i < size ; ++i)
mark[nodes[i]] = false;
components.push_back(nodes);
}
void DepthFirstSearch (int node, int number, int father)
{
low[node] = dfn[node] = number;
unsigned int i, size(graph[node].size());
int neighbor;
for (i = 0 ; i < size ; ++i)
{
neighbor = graph[node][i];
if (neighbor == father)
continue;
if (dfn[neighbor])
low[node] = min(low[node],dfn[neighbor]);
else
{
stack.push(std::make_pair(node,neighbor));
DepthFirstSearch(neighbor,number + 1,node);
low[node] = min(low[node],low[neighbor]);
if (low[neighbor] >= dfn[node])
// node is an articulation point
BiconnectedComponent(node,neighbor);
}
}
}
int main (void)
{
read();
for (int node(1) ; node <= n ; ++node)
if (!dfn[node])
DepthFirstSearch(node,1,1);
print();
return 0;
}