首页 > 搜索 > DFS搜索 > HDU 3394-Railway-DFS-[解题报告]HOJ
2014
03-23

HDU 3394-Railway-DFS-[解题报告]HOJ

Railway

问题描述 :

There are some locations in a park, and some of them are connected by roads. The park manger needs to build some railways along the roads, and he would like to arrange tourist routes to each circuit. If a railway belongs to more than one tourist routes, there might be clash on it, and if a railway belongs to none tourist route, it doesn’t need to build.
Now we know the plan, and can you tell us how many railways are no need to build and how many railways where clash might happen.

输入:

The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.

输出:

The Input consists of multiple test cases. The first line of each test case contains two integers, n (0 < n <= 10000), m (0 <= m <= 100000), which are the number of locations and the number of the railways. The next m lines, each line contains two integers, u, v (0 <= u, v < n), which means the manger plans to build a railway on the road between u and v.
You can assume that there is no loop and no multiple edges.
The last test case is followed by two zeros on a single line, which means the end of the input.

样例输入:

8 10
0 1
1 2
2 3
3 0
3 4
4 5
5 6
6 7
7 4
5 7
0 0

样例输出:

1 5


题意描述
        公园有n个景点,公园的管理员计划要建m条道路,并且安排一些形成回路的参观路径,如果一条道路可以被多条回路共用,
        那么这条边是冲突边,如果一个块中有多个环,则该块中的每条边都是冲突边。
        如果不能形成环的路则为不需要的边,现在就是求无向图中冲突边和不需要边的条数

解题思路:
        把图分为多个块,然后判断每个块里面的边数,如果块的边数等于块的点数,那么该块只有一个环,如果块的边数大于块的
       点数,那么这个块中有多个环,并且这个块中的每条边都是多个环里面的一部分。

注意:  将块出栈时,只能出到u的子节点v为止 ,因为u作为割点极有可能是该个块与别的块公用的,所以若是每次出栈到u,则会破坏其他的块。(这就是与有向图的tarjan的一个不同之处。)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N=11000;
const int M=210000;
using namespace std;

int head[N],to[M],next[M],edge_cnt,n,m;
int dfs_cnt,dfn[N],low[N],num[N],in[N];
stack<int> s;
void init_edge(){
    memset(head,-1,sizeof(head)); edge_cnt=0;
}
void add_edge(int u,int v){
    next[edge_cnt]=head[u]; to[edge_cnt]=v; head[u]=edge_cnt++;
    next[edge_cnt]=head[v]; to[edge_cnt]=u; head[v]=edge_cnt++;
}

int ans1,ans2;
vector<int> block;

void update(){
    int sz=block.size(),cnt=0;
    for (int i=0;i<sz;++i){
        int u=block[i];
        for (int j=head[u];j!=-1;j=next[j]){
            int v=to[j];
            if (in[v]) cnt++;
        }
    }
    cnt/=2;
    if (cnt>sz) ans2+=cnt;
    else if (cnt<sz) ans1+=cnt;
}

void dfs(int u,int fa){
    low[u]=dfn[u]=++dfs_cnt;
    s.push(u);
    for (int i=head[u];i!=-1;i=next[i]){
        int v=to[i];
        if (!dfn[v]){
            dfs(v,u); low[u]=min(low[v],low[u]);
            if (low[v]>=dfn[u]){
                block.clear(); memset(in,0,sizeof(in));
                int tmp;
                do{
                    tmp=s.top(); s.pop();
                    in[tmp]=1; block.push_back(tmp);
                }while (tmp!=v);
                block.push_back(u); in[u]=1;
                update();
            }
        }
        else if (fa!=v) low[u]=min(low[u],dfn[v]);
    }
}

void init(){
    memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low));
    memset(num,0,sizeof(num)); memset(in,0,sizeof(in));
    while (!s.empty()) s.pop();
    dfs_cnt=0;
}

void work(){
    ans1=ans2=0; init();
    for (int i=1;i<=n;++i)
        if (!dfn[i]) dfs(i,-1);
    printf("%d %d\n",ans1,ans2);
}
int main(){
    while (~scanf("%d%d",&n,&m) && (n+m)){
        init_edge();
        for (int i=1;i<=m;++i){
            int u,v; scanf("%d%d",&u,&v);
            add_edge(u+1,v+1);
        }
        work();
    }
    return 0;
}

参考:http://blog.csdn.net/qq397470071/article/details/20872583


, ,
  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish