javaweb监听器接口-观察者模式
259
2022-09-10
poj2942 Knights of the Round Table
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 13552 | Accepted: 4538 |
Description
Input
Output
Sample Input
5 5 1 4 1 5 2 5 3 4 4 5 0 0
Sample Output
2
Hint
Source
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1010,maxm = 1e6+5; int head[maxn],to[maxm * 2],nextt[maxm * 2],tot = 1; int n,m,a[maxn][maxn],num,ans,dfs_clock,top,pre[maxn],low[maxn],iscut[maxn],belong[maxn],col[maxn]; bool flag[maxn]; struct node { int u,v; }e[maxm * 2]; void add(int x,int y) { to[tot] = y; nextt[tot] = head[x]; head[x] = tot++; } bool color(int u,int id) { for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (belong[v] != id) continue; if (col[v] == col[u]) return false; if (!col[v]) { col[v] = 3 - col[u]; if (!color(v,id)) return false; } } return true; } void dfs(int u,int fa) { pre[u] = low[u] = ++dfs_clock; int child = 0; for (int i = head[u];i;i = nextt[i]) { int v = to[i]; if (!pre[v]) { node temp; temp.u = u; temp.v = v; e[++top] = temp; child++; dfs(v,u); low[u] = min(low[u],low[v]); if (low[v] >= pre[u]) { iscut[u] = 1; num++; while (1) { int tu = e[top].u,tv = e[top--].v; if (belong[tu] != num) belong[tu] = num; if (belong[tv] != num) belong[tv] = num; if (tu == u && tv == v) break; } col[u] = 1; if (!color(u,num)) for (int i = 1; i <= n; i++) if (belong[i] == num) flag[i] = 1; col[u] = 0; } } else if (pre[v] < pre[u] && v != fa) { node temp; temp.u = u; temp.v = v; e[++top] = temp; low[u] = min(low[u],pre[v]); } } if (child == 1 && fa == -1) iscut[u] = 0; } void bcc() { for (int i = 1; i <= n; i++) if (!pre[i]) dfs(i,-1); } int main() { while (scanf("%d%d",&n,&m) == 2 && (n || m)) { memset(head,0,sizeof(head)); memset(a,0,sizeof(a)); memset(flag,false,sizeof(flag)); memset(pre,0,sizeof(pre)); memset(low,0,sizeof(low)); memset(iscut,0,sizeof(iscut)); memset(col,0,sizeof(col)); memset(belong,0,sizeof(belong)); tot = 1; ans = 0; dfs_clock = 0; top = 0; num = 0; for (int i = 1; i <= m; i++) { int u,v; scanf("%d%d",&u,&v); a[u][v] = a[v][u] = 1; } for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) if (!a[i][j]) { add(i,j); add(j,i); } bcc(); for (int i = 1; i <= n; i++) if (!flag[i]) ans++; printf("%d\n",ans); } return 0; }
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~