【t082】牛跑步

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

【题解】

枚举第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
",len);
    rep1(i,0,len-1)
        {
            printf("%d",v[i]);
            if (i==len-1)
                puts("");
            else
                putchar(' ');
        }
    return 0;
}