先放这吧，没时间写，明天再补

“明天到了”

题目链接

题意：求不在任何奇环内的点的数量。

Tarjan求点双联通分量，然后再染色判断是不是二分图就好了。

只是不懂为什么Tarjan求双联通分量时要用栈保存点对，希望大佬留言帮助。

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

inline int min(int a, int b){

    return a > b ? b : a;

}

inline int max(int a, int b){

    return a > b ? a : b;

}

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

const int MAXN = 1010;

const int MAXM = 1000010;

int n, m;

int a, b;

int s[MAXN][MAXN];

struct Edge{

    int next, to;

}e[MAXM << 1];

int head[MAXN], num;

inline void Add(int from, int to){

    e[++num].to = to;

    e[num].next = head[from];

    head[from] = num;

}

int dfn[MAXN], low[MAXN], ID, color[MAXN], can[MAXN], belong[MAXN], top, ans, cnt;

struct point{

    int u, v;

}stack[MAXN << 2];

vector <int> dcc[MAXN];

bool Judge(int u, int Color, int now){

    color[u] = Color;

    for(int i = head[u]; i; i = e[i].next){

       if(belong[e[i].to] != now) continue;

       if(!color[e[i].to])

         if(Judge(e[i].to, 3 - Color, now)) return true;

         else;

       else

         if(color[e[i].to] == color[u])

           return true;

    }

    return false;

}

void Tarjan(int u, int fa){

    dfn[u] = low[u] = ++ID;

    for(int i = head[u]; i; i = e[i].next){

       if(!dfn[e[i].to]){

         stack[++top] = (point){ u, e[i].to };

         Tarjan(e[i].to, u);

         low[u] = min(low[u], low[e[i].to]);

         if(low[e[i].to] >= dfn[u]){

           dcc[++cnt].clear();

           point now;

           do{

             now = stack[top--];

             if(belong[now.u] != cnt) belong[now.u] = cnt, dcc[cnt].push_back(now.u);

             if(belong[now.v] != cnt) belong[now.v] = cnt, dcc[cnt].push_back(now.v);

           }while(now.u != u || now.v != e[i].to);

         }

       }

       else if(dfn[e[i].to] < dfn[u] && e[i].to != fa)

         stack[++top] = (point){ u, e[i].to }, low[u] = min(low[u], dfn[e[i].to]);

    }

}

int main(){

    while(233){

      n = read(); m = read();

      if(!n && !m) break;

      memset(s, 0, sizeof s);

      memset(dfn, 0, sizeof dfn);

      memset(low, 0, sizeof low);

      memset(can, 0, sizeof can);

      memset(head, 0, sizeof head);

      memset(color, 0, sizeof color);

      memset(belong, 0, sizeof belong);

      ID = ans = top = num = cnt = 0;

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

         a = read(); b = read();

         s[a][b] = s[b][a] = 1;

      }

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

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

            if(!s[i][j])

              Add(i, j), Add(j, i);

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

         if(!dfn[i])

           Tarjan(i, 0);

      for(int i = 1; i <= cnt; ++i){

         memset(color, 0, sizeof color);

         for(int j = 0; j < dcc[i].size(); ++j)

            belong[dcc[i][j]] = i;

         if(Judge(dcc[i][0], 1, i)){

           for(int j = 0; j < dcc[i].size(); ++j)

              can[dcc[i][j]] = 1;

         }

      }

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

         if(!can[i])

           ++ans;

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

    }

    return 0;

}