Pagini recente » Cod sursa (job #1951998) | Cod sursa (job #1359474) | Cod sursa (job #1908595) | Cod sursa (job #2831875) | Cod sursa (job #859071)
Cod sursa(job #859071)
#include <cstdio>
const int MAX_N(100001);
int n, m, components;
int component_size [MAX_N];
int component [MAX_N], add_node;
int link [MAX_N], low_link [MAX_N];
bool out_stack [MAX_N];
struct list
{
int node;
struct list *next;
} *graph [MAX_N];
struct edge
{
int x;
int y;
} stack [MAX_N];
inline bool operator != (struct edge a, struct edge b)
{
return (a.x != b.x && a.y != b.y);
}
inline struct edge make_edge (int x, int y)
{
struct edge result;
result.x = x;
result.y = y;
return result;
}
inline int min (int a, int b)
{
return a < b ? a : b;
}
int top;
inline void add (int x, int y)
{
struct list *new_edge(new struct list);
new_edge->node = y;
new_edge->next = graph[x];
graph[x] = new_edge;
}
inline void read (void)
{
std::freopen("biconex.in","r",stdin);
std::scanf("%d %d",&n,&m);
int x, y;
for (int counter(0) ; counter < m ; ++counter)
{
std::scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
std::fclose(stdin);
}
inline void print (void)
{
std::freopen("biconex.out","w",stdout);
std::printf("%d\n",components);
int i(0), j(0);
for (int index(0) ; index < components ; ++index)
{
for (j += component_size[index] ; i < j ; ++i)
std::printf("%d ",component[i]);
std::putchar('\n');
}
std::fclose(stdout);
}
inline void push (const struct edge &e)
{
stack[top] = e;
++top;
}
void BiconnectedComponent (const struct edge &e)
{
int size(0);
do
{
--top;
if (!out_stack[stack[top].x])
{
component[add_node] = stack[top].x;
++add_node;
++size;
out_stack[stack[top].x] = true;
}
if (!out_stack[stack[top].y])
{
component[add_node] = stack[top].y;
++add_node;
++size;
out_stack[stack[top].y] = true;
}
}
while (stack[top] != e);
component_size[components] = size;
++components;
for (int index(add_node - size) ; index < add_node ; ++index)
out_stack[component[index]] = false;
}
void DepthFirstSearch (const int node, const int father, const int depth)
{
struct edge e;
link[node] = low_link[node] = depth;
for (struct list *iterator(graph[node]) ; iterator ; iterator = iterator->next)
{
if (iterator->node == father)
continue;
if (link[iterator->node])
low_link[node] = min(low_link[node],link[iterator->node]);
else
{
e.x = node;
e.y = iterator->node;
push(e);
DepthFirstSearch(iterator->node,node,depth + 1);
low_link[node] = min(low_link[node],low_link[iterator->node]);
if (low_link[iterator->node] >= link[node])
BiconnectedComponent(make_edge(node,iterator->node));
}
}
}
int main (void)
{
read();
DepthFirstSearch(1,0,1);
print();
return 0;
}