Pagini recente » Cod sursa (job #2788550) | Cod sursa (job #2605974) | Cod sursa (job #2857453) | Cod sursa (job #2428132) | Cod sursa (job #856511)
Cod sursa(job #856511)
#include <cstdio>
const int MAX_N(100001);
int n, m;
struct list
{
int node;
struct list *next;
} *graph [MAX_N];
int stack [MAX_N], top;
int components;
int component [MAX_N], index;
int component_size [MAX_N];
int identifier;
int link [MAX_N];
int lower_link [MAX_N];
bool in_stack [MAX_N];
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("ctc.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);
}
std::fclose(stdin);
}
inline void print (void)
{
std::freopen("ctc.out","w",stdout);
std::printf("%d\n",components);
int i, j(0), end(0);
for (i = 0 ; i < components ; ++i)
{
end += component_size[i];
while (j < end)
{
std::printf("%d ",component[j]);
++j;
}
std::putchar('\n');
}
std::fclose(stdout);
}
inline int min (int a, int b)
{
return a < b ? a : b;
}
inline void StronglyConnectedComponents (int root)
{
int size(0);
do
{
--top;
component[index] = stack[top];
in_stack[component[index]] = false;
++index;
++size;
}
while (stack[top] != root);
component_size[components] = size;
++components;
}
void DepthFirstSearch (int vertex)
{
++identifier;
link[vertex] = lower_link[vertex] = identifier;
stack[top] = vertex;
++top;
in_stack[vertex] = true;
for (struct list *iterator(graph[vertex]) ; iterator ; iterator = iterator->next)
{
if (link[iterator->node])
{
if (in_stack[iterator->node])
lower_link[vertex] = min(lower_link[vertex],lower_link[iterator->node]);
}
else
{
DepthFirstSearch(iterator->node);
lower_link[vertex] = min(lower_link[vertex],lower_link[iterator->node]);
}
}
if (link[vertex] == lower_link[vertex])
StronglyConnectedComponents(vertex);
}
inline void Tarjan (void)
{
for (int vertex(1) ; vertex <= n ; ++vertex)
if (!link[vertex])
DepthFirstSearch(vertex);
}
int main (void)
{
read();
Tarjan();
print();
return 0;
}