New Reform---cf659E（dfs找环）

题目链接：http://codeforces.com/problemset/problem/659/E

给你n个点，m条双向边，然后让你把这些边变成有向边，使得最后的图中入度为0的点的个数最少，求最少的点的个数；

我们很容易的看出当一个点所在的图中存在环时，那么这里面的所有点都可以入度不为0，当不存在的时候最少有一个点的入度为0；

dfs学的不好，所以没做出来；

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <map>

#include <vector>

using namespace std;

typedef long long LL;

#define N 100100

#define met(a, b) memset(a, b, sizeof(a))

int flag, vis[N], n, f[N];

vector<vector<int> >G;

void dfs(int u, int fa)

{

    if(vis[u])///当再次访问过这个点的时候说明存在环了

    {

        flag = ;

        return;

    }

    vis[u] = ;

    f[u] = fa;///

    int len = G[u].size();

    for(int i=; i<len; i++)

    {

        int v = G[u][i];

        if( f[u]!=v )

            dfs(v, u);

    }

}

int main()

{

    int m, u, v;

    while(scanf("%d %d", &n, &m)!=EOF)

    {

        G.clear();

        G.resize(n+);

        met(vis, );

        met(f, -);

        for(int i=; i<=m; i++)

        {

            scanf("%d %d", &u, &v);

            G[u].push_back(v);

            G[v].push_back(u);

        }

        int ans = ;

        for(int i=; i<=n; i++)

        {

            if(!vis[i])///当这个点还没被访问过时；

            {

                flag = ;

                dfs(i, -);

                if(!flag)

                    ans++;

            }

        }

        printf("%d\n", ans);

    }

    return ;

}