|
2200 struct node{ int u , v ; int next ; } edge[2100000]; int head[maxn] , cnt , vis[2100000] ; int temp[maxn] , color[maxn] ; int dnf[maxn] , low[maxn] , time ; int Map[maxn][maxn] , ans[maxn] ; stack
sta; vector
vec[maxn] ; int num ; void init() { memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(Map,0,sizeof(Map)); memset(dnf,0,sizeof(dnf)); memset(low,0,sizeof(low)); memset(temp,0,sizeof(temp)); memset(ans,0,sizeof(ans)); cnt = time = num = 0 ; } void add(int u,int v) { while( !sta.empty() ) sta.pop(); edge[cnt].u = u ; edge[cnt].v = v ; edge[cnt].next = head[u] ; head[u] = cnt++ ; edge[cnt].u = v ; edge[cnt].v = u ; edge[cnt].next = head[v] ; head[v] = cnt++ ; } void tarjan(int u) { dnf[u] = low[u] = ++time ; int i , j , v ; for(i = head[u] ; i != -1 ; i = edge[i].next) { if(vis[i]) continue ; vis[i] = vis[i^1] = 1 ; v = edge[i].v ; if( !dnf[v] ) { sta.push(i) ; tarjan(v); low[u] = min( low[u],low[v] ) ; if( low[v] >= dnf[u] ) { num++ ; vec[num].clear(); while(1) { j = sta.top(); sta.pop(); vec[num].push_back(edge[j].u); vec[num].push_back(edge[j].v); if( edge[j].u == u && edge[j].v == v ) break; } } } else if( dnf[v] < dnf[u] ) { sta.push(i) ; low[u] = min( low[u],dnf[v] ); } } } int dey(int u,int k) { int i ,v ; for(i = head[u] ; i != -1 ; i = edge[i].next) { v = edge[i].v ; if( temp[v] != k ) continue ; if( color[v] == color[u] ) return 0 ; if( !color[v] ) { color[v] = 3 - color[u] ; if( !dey(v,k) ) return 0 ; } } return 1 ; } int main() { int n , m , u , v , i , j ; while(scanf("%d %d", &n, &m) && (n+m) != 0 ) { init(); while(m--) { scanf("%d %d", &u, &v); Map[u][v] = Map[v][u] = 1 ; } for(i = 1 ; i <= n ; i++) for(j = i+1 ; j <= n ; j++) if( !Map[i][j] ) add(i,j); for(i = 1 ; i <= n ; i++) if( !dnf[i] ) tarjan(i); for(i = 1 ; i <= num ; i++) { if( vec[i].size() < 3 ) continue ; for(j = 0 ; j < vec[i].size() ; j++) temp[ vec[i][j] ] = i ; memset(color,0,sizeof(color)); u = vec[i][0] ; color[u] = 1 ; if( !dey(u,i) ) { for(j = 0 ; j < vec[i].size(); j++) ans[ vec[i][j] ] = 1 ; } } m = n ; for(i = 1 ; i <= n ; i++) if( ans[i] ) m-- ; printf("%d\n", m); } return 0; }
|