【t082】牛跑步

分手后的思念是犯贱 2021-10-23 09:13 237阅读 0赞

Time Limit: 1 second  
Memory Limit: 128 MB

【问题描述】

新牛到部队，CG要求它们每天早上搞晨跑，从A农场跑到B农场。从A农场到B农场中有n-2个路口，分别标上号，A农场为1号，B农场  
为n号，路口分别为2…n-1号，从A 农场到B农场有很多条路径可以到达，而CG发现有的路口是必须经过的，即每条路径都经过  
的路口，CG要把它们记录下来，这样CG就可以先到那个路口，观察新牛们有没有偷懒，而你的任务就是找出所有必经路口。  
【输入格式】

第一行两个用空格隔开的整数n（3≤n≤2000）和e（1≤e≤8000）。  
接下来从第2到第e+1行，每行两个用空格隔开的整数p和q，表示路口p和q之间有路径直达。  
输入数据保证必经路口一定存在，并且每个路口都和A农场、B农场相连通。

【输出格式】

第一行一个整数m，表示必经路口的数目。  
第二行按从小到大的顺序依次输出每个必经路口的编号，每两个数之间用一个空格隔开。  
注意：不包括起点和终点。

Sample Input

6 6  
1 2  
2 4  
2 3  
3 5  
4 5  
5 6

Sample Output

2  
2 5

【题目链接】:[http://noi.qz5z.com/viewtask.asp?id=t082][http_noi.qz5z.com_viewtask.asp_id_t082]

【题解】  
  
枚举第i个点;  
把这个点删掉;(dfs的时候忽略这个点就好);  
然后从点1开始dfs;  
看看能不能从点1到点n;  
如果不可以到n那么就表明删掉的这个点是个必经点;  
(会有环。。所以加个bool数组吧。不然9个RE在等着你)  
  
【完整代码】

#include <cstdio>
    #include <vector>
    using namespace std;
    #define rei(x) scanf("%d",&x)
    #define rep1(i,x,y) for (int i = x;i <= y;i++)
    #define pb push_back
    
    const int MAXN = 2e3+100;
    
    int n,e,dd;
    bool bo[MAXN];
    vector <int> G[MAXN],v;
    
    void dfs(int x)
    {
        bo[x] = true;
        int len = G[x].size();
        rep1(i,0,len-1)
        {
            int y = G[x][i];
            if (!bo[y] && y!=dd)
                dfs(y);
        }
    }
    
    int main()
    {
        //freopen("F:\\rush.txt","r",stdin);
        rei(n);rei(e);
        rep1(i,1,e)
        {
            int x,y;
            rei(x);rei(y);
            G[x].pb(y);
            G[y].pb(x);
        }
        rep1(ee,2,n-1)
        {
            rep1(i,1,n)
                bo[i] = false;
            dd = ee;
            bo[1] = true;
            dfs(1);
            if (!bo[n])
                v.pb(ee);
        }
        int len = v.size();
        printf("%d\n",len);
        rep1(i,0,len-1)
            {
                printf("%d",v[i]);
                if (i==len-1)
                    puts("");
                else
                    putchar(' ');
            }
        return 0;
    }

转载于:https://www.cnblogs.com/AWCXV/p/7626696.html

[http_noi.qz5z.com_viewtask.asp_id_t082]: http://noi.qz5z.com/viewtask.asp?id=t082