PTA Strongly Connected Components

Write a program to find the strongly connected components in a digraph.

Format of functions:

void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) );

where Graph is defined as the following:

typedef struct VNode *PtrToVNode;
struct VNode {
    Vertex Vert;
    PtrToVNode Next;
};
typedef struct GNode *Graph;
struct GNode {
    int NumOfVertices;
    int NumOfEdges;
    PtrToVNode *Array;
};

Here void (*visit)(Vertex V) is a function parameter that is passed into StronglyConnectedComponents to handle (print with a certain format) each vertex that is visited. The function StronglyConnectedComponents is supposed to print a return after each component is found.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

#define MaxVertices 10  /* maximum number of vertices */
typedef int Vertex;     /* vertices are numbered from 0 to MaxVertices-1 */
typedef struct VNode *PtrToVNode;
struct VNode {
    Vertex Vert;
    PtrToVNode Next;
};
typedef struct GNode *Graph;
struct GNode {
    int NumOfVertices;
    int NumOfEdges;
    PtrToVNode *Array;
};

Graph ReadG(); /* details omitted */

void PrintV( Vertex V )
{
   printf("%d ", V);
}

void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) );

int main()
{
    Graph G = ReadG();
    StronglyConnectedComponents( G, PrintV );
    return 0;
}

/* Your function will be put here */

Sample Input (for the graph shown in the figure):

4 5
0 1
1 2
2 0
3 1
3 2

Sample Output:

3
1 2 0

Note: The output order does not matter. That is, a solution like

0 1 2
3

is also considered correct.

这题目就是直接照搬Tarjan算法实现就好了,一个讲Tarjan算法讲的很好的blog:http://blog.csdn.net/acmmmm/article/details/16361033 还有Tarjan算法实现的具体代码:http://blog.csdn.net/acmmmm/article/details/9963693 都是一个ACM大佬写的,其实我也看了很久才看懂Tarjan算法是干啥的……毕竟上课从来不听不知道老师讲的方法是怎么样的……

直接放代码吧:

//
//  main.c
//  Strongly Connected Components
//
//  Created by 余南龙 on 2016/12/6.
//  Copyright ? 2016年 余南龙. All rights reserved.
//

int dfn[MaxVertices], low[MaxVertices], stack[MaxVertices], top, t, in_stack[MaxVertices];

int min(int a, int b){
    if(a < b){
        return a;
    }
    else{
        return b;
    }
}

void Tarjan(Graph G, int v){
    PtrToVNode node = G->Array[v];
    int son, tmp;

    dfn[v] = low[v] = ++t;
    stack[++top] = v;
    in_stack[v] = 1;

    while(NULL != node){
        son = node->Vert;
        if(-1 == dfn[son]){
            Tarjan(G, son);
            low[v] = min(low[son], low[v]);
        }
        else if(1 == in_stack[son]){
            low[v] = min(low[v], dfn[son]);
        }
        node = node->Next;
    }
    if(dfn[v] == low[v]){
        do{
            tmp = stack[top--];
            printf("%d ", tmp);
            in_stack[tmp] = 0;
        }while(tmp != v);
        printf("\n");
    }
}

void StronglyConnectedComponents( Graph G, void (*visit)(Vertex V) ){
    int i;

    for(i = 0; i < MaxVertices; i++){
        dfn[i] = -1;
        low[i] = in_stack[i] = 0;
    }
    top = -1;
    t = 0;

    for(i = 0; i < G->NumOfVertices; i++){
        if(-1 == dfn[i]){
            Tarjan(G, i);
        }
    }
}
时间: 12-05

PTA Strongly Connected Components的相关文章

Strongly connected components

拓扑排列可以指明除了循环以外的所有指向,当反过来还有路可以走的话,说明有刚刚没算的循环路线,所以反过来能形成的所有树都是循环

Giraph添加应用程序Weakly Connected Components算法

本人原创,转载请注明出处! 本人QQ:530422429,欢迎大家指正.讨论. 目的:举例说明如何在Giraph中添加应用程序,以WCC(Weakly Connected Components)算法为例,描述怎么添加Vertex的子类,自定义输入输出格式和使用Combiner等. 背景:Giraph源码中自带有WCC算法,类为:org.apache.giraph.examples.ConnectedComponentsVertex,代码如下: package org.apache.giraph.

HDU 4635 —— Strongly connected——————【 强连通、最多加多少边仍不强连通】

Strongly connected Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4635 Description Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can

HDU 4635 Strongly connected (有向图的强连通分量)

Strongly connected Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description Give a simple directed graph with N nodes and M edges. Please tell me the maximum number of the edges you can add that the grap

[tarjan] hdu 4635 Strongly connected

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4635 Strongly connected Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1568    Accepted Submission(s): 654 Problem Description Give a simple dir

Number of Connected Components in an Undirected Graph -- LeetCode

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph. Example 1: 0 3 | | 1 --- 2 4 Given n = 5 and edges = [[0, 1], [1,

hdu 4635 Strongly connected (tarjan)

题意:给一个n个顶点m条弧的简单有向图(无环无重边),求最多能够加入多少条弧使得加入后的有向图仍为简单有向图且不是一个强连通图.假设给的简单有向图本来就是强连通图,那么输出-1. 分析: 1.用tarjan算法求出强连通分量的个数,假设个数为1,那么输出-1,结束,否则运行2 2.如果将一些强连通分量合并为有n1个顶点简单全然图1,而将剩下的强连通分量合并为n2个顶点的简单全然图2,跨这两个简单全然图的弧的方向仅仅能是单向的,如果m1为全然图1内部的弧的数量,m2为为全然图2内部的弧的数量.m3

Hdu 4635 Strongly connected

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4635 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 100005; 9 const int INF

HDU 4635 Strongly connected(强连通分量,变形)

题意:给出一个有向图(不一定连通),问最多可添加多少条边而该图仍然没有强连通. 思路: 强连通分量必须先求出,每个强连通分量包含有几个点也需要知道,每个点只会属于1个强连通分量. 在使图不强连通的前提下,要添加尽可能多的边.边至多有n*(n-1)条,而已经给了m条,那么所能添加的边数不可能超过k=n*(n-1)-m. 这k条边还有部分不能添加,一添加立刻就强连通.一个强连通图最少只需要n条边,根据强连通的特性,缩点之后必定是不会有环的存在的,那么只要继续保持没有环的存在即可.我们只要让其中1个强