学步园

 边双连通分量求解要点：

1.通过割点找变双连通分量。

2.点入栈，当前边（u->v）的v点等于栈顶的点时停止出栈。

3.每个割点可能属于多个连通分量。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn 1010
#define maxm 1000009
int min(int a, int b) {return a < b ? a : b;}

bool map[maxn][maxn];

struct E
{
    int v, next;
}edge[maxm<<3];

int head[maxn], tot;
int n, m;
void add(int s, int t)
{
    edge[tot].v = t;
    edge[tot].next = head[s];
    head[s] = tot++;

    edge[tot].v = s;
    edge[tot].next = head[t];
    head[t] = tot++;
}

int stack[maxn], top;
int dfn[maxn], low[maxn];
int num, id;
vector<int> ans[maxn];
void dfs(int u, int fa)
{
    int i;
    low[u] = dfn[u] = ++id;
    stack[++top] = u;
    for(i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == fa) continue; // 该题无重边，所以这一步骤就是去掉了一条树边的反向边
        if(!dfn[v])
        {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(dfn[u] <= low[v])
            {
                ans[num].push_back(u);
                while(1)
                {
                    int w = stack[top--];
                    ans[num].push_back(w);
                    if(w == v) break;
                }
                if(ans[num].size()<=2) ans[num].clear();
                else num++;
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

int col[maxn];
bool color(int u, int fa, int k)
{
    int i;
    for(i = 0; i < ans[k].size(); i++)
    {
        int y = ans[k][i];
        if(fa == i || !map[ans[k][u]][y]) continue;
        if(col[i] == -1) 
        {
            col[i] = 1^col[u];
            if( color(i, u, k) ) return 1;
        }
        else if(col[i] == col[u]) return 1;
    }
    return 0;
}

bool vis[maxn];
void solve()
{
    num = 0; top = 0;
    memset(dfn, 0, sizeof(int)*(n+1));
    int i;
    for(i = 1; i <= n; i++)
        if(!dfn[i]) id = 0, dfs(i, -1);
    memset(vis, 0, sizeof(int)*(n+1));
    for(i = 0; i < num; i++)
    {
        memset(col, -1, sizeof(int)*(n+1));
        col[0] = 1;
        if(color(0, -1, i))
        {
            for(int x = 0; x < ans[i].size(); x++)
                vis[ans[i][x]] = 1;
        }
    }    
    int cnt = 0;
    for(i = 1; i <= n; i++)
        if(!vis[i]) cnt++;
    printf("%d\n", cnt);
}
int main()
{
    int i, j;
    while( ~scanf("%d%d", &n, &m) && n && m)
    {
        fill(&map[0][0], &map[n+1][n+1]+1, 1);
        int x, y;
        for(i = 0; i <= n; i++)
        {
            ans[i].clear();
            map[i][i] = 0;
        }
        while(m--)
        {
            scanf("%d%d", &x, &y);
            map[x][y] = map[y][x] = 0;
        }
        memset(head, -1, sizeof(int)*(n+1));
        tot = 0;
        for(i = 1; i <= n; i++)
            for(j = i+1; j <= n; j++)
                if(map[i][j]) add(i, j);
        solve();
    }
    return 0;
}