首页 > ACM题库 > HDU-杭电 > HDU 1269 迷宫城堡-DFS-[解题报告] C++
2013
12-04

HDU 1269 迷宫城堡-DFS-[解题报告] C++

迷宫城堡

问题描述 :

为了训练小希的方向感,Gardon建立了一座大城堡,里面有N个房间(N<=10000)和M条通道(M<=100000),每个通道都是单向的,就是说若称某通道连通了A房间和B房间,只说明可以通过这个通道由A房间到达B房间,但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的,即:对于任意的i和j,至少存在一条路径可以从房间i到房间j,也存在一条路径可以从房间j到房间i。

输入:

输入包含多组数据,输入的第一行有两个数:N和M,接下来的M行每行有两个数a和b,表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。

输出:

对于输入的每组数据,如果任意两个房间都是相互连接的,输出"Yes",否则输出"No"。

样例输入:

3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0

样例输出:

Yes
No

题意:判断是否存在从任意一个起点开始都可以走完余下任何一个点。

解题思路:有向联通图,判断联通分量是否为1。

解题补充知识点:在有向图G中,如果两个顶点间至少存在一条路径,称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通,称G是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通分量(strongly connected components)。有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1269

#include <iostream>
using namespace std;
#include <stack>
#include <vector>
const int MAX=10000+10;
vector<int >map[MAX];//构建邻接表
stack<int >s;//将更新到的店入栈
int Dfs[MAX];//访问的节点次序//u或u的子树能够追溯到的最早的栈中节点的序号(时间戳)
int Low[MAX];//父节点最早出现的时间戳//节点u搜索的序号(时间戳)
bool isStack[MAX];//是否在栈中
int used[MAX];//标记该点输入哪个联通分量
int top;//时间戳
int newflag;//联通分量
void init()//各种初始化
{
    memset(Dfs,0,sizeof(Dfs));
    memset(Low,0,sizeof(Low));
    memset(isStack,false,sizeof(isStack));
    memset(used,0,sizeof(used));
    for(int i=0;i<MAX;i++)
    {
        map[i].clear();
    }
    while(!s.empty())
    {
        s.pop();
    }
    newflag=0;
    top=0;
}
void tarjan(int u)
{
    Dfs[u]=Low[u]=++top;//时间戳
    isStack[u]=true;//存在栈中
    s.push(u);
    for(int x=0;x<map[u].size();x++)
    {
        int v=map[u][x];
        if(!Dfs[v])//判断是否更新过
        {
            tarjan(v);//递归,继续更新
            if(Low[v]<Low[u])//若存在子节点能找到比父节点更早节点,即有环
            {
                Low[u]=Low[v];
            }
        }
        else if(isStack[v]&&Dfs[v]<Low[u])
        {
            Low[u]=Dfs[v];
        }
    }
    if(Dfs[u]==Low[u])//找不到邻接点了,即找到联通分量的结束条件
    {
        newflag++;
        int x;
        do
        {
            x=s.top();
            isStack[x]=false;
            used[x]=newflag;
            s.pop();
        }while(x!=u);//输出联通分量
    }
    return;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m),n+m)
    {
        init();
        for(int i=0;i<m;i++)
        {
            int x,y;
            cin>>x>>y;
            map[x].push_back(y);
        }
        for(i=1;i<=n;i++)
        {
            if(!Dfs[i])
            {
                tarjan(i);
            }
        }
        if(newflag==1)
        {
            printf("Yes\n");
        }
        else printf("No\n");
    }
    return 0;
}

 


, ,
  1. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }