请说明网站建设的一般过程包括哪些,网站怎么更新,建网站的详细技术,动画制作学什么专业题目描述 圆桌骑士是一个非常吸引人的职业。因此#xff0c;在最近几年里#xff0c;亚瑟王史无前例的扩招圆桌骑士#xff0c;并不令人惊讶。现在这里有许多圆桌骑士#xff0c;每个圆桌骑士都收到一份珍贵的邀请函#xff0c;被邀请去英灵殿圆桌。这些骑士将要环绕着坐在… 题目描述 圆桌骑士是一个非常吸引人的职业。因此在最近几年里亚瑟王史无前例的扩招圆桌骑士并不令人惊讶。现在这里有许多圆桌骑士每个圆桌骑士都收到一份珍贵的邀请函被邀请去英灵殿圆桌。这些骑士将要环绕着坐在一个圆桌旁但通常只有一小部分骑士会来因为剩下的骑士正忙着在全国各地为人民服务。 不幸的是这些圆桌骑士的酒量不行很容易喝高。当他们喝高时一些不幸的便当事件将会发生。因此亚瑟王请来了长门大神来确保在未来不会有类似的事情发生。在仔细分析了这个问题后长门大神意识到要想避免骑士之间相互斗殴当且仅当他们在圆桌旁所坐的位置符合以下条件 1. 某些骑士之间有仇避免相互之间有仇的骑士挨在一块。 2. 当场上有偶数个骑士时若通过投票解决问题的话正方与反方的票数可能相同这会令骑士们非常不爽。因此只能有奇数个骑士坐在圆桌旁。 长门大神会尽量的满足以上两个条件否则她会代替亚瑟王宣布散会若只有一个骑士在场的话也会宣布散会因为一个骑士不管怎么坐都不可能环绕一个圆桌。这将意味着无论如何安排一些骑士都无法到场无法坐在圆桌旁边其中一种情况即为当这个骑士对所有骑士都有仇时当然还可能是其他情况。若一个圆桌骑士永远无法到场则这个骑士就失去了“圆桌”的意义他将会被开除。这些骑士将会被降级降到诸如“爱的战士”“蘑菇骑士”“人鱼骑士”之类的职阶。 为了帮助长门大神你必须写一个程序来计算会有多少圆桌骑士会被开除。 输入 输入有多组每组第一行两个整数N和MN为骑士的数量。 接下来M行每行两个整数i,j表示i与j之间有仇恨。 输入数据保证不会有重边和自环。 0 0 代表输入结束 输出 一个整数为所求的答案。 样例输入 5 51 21 32 32 43 50 0 样例输出 2 提示 1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000 步骤 1.先将没有仇恨的骑士两两建边。 2.求一遍双连通分量。 3.在同一连通分量里面找奇环若该连通分量存在奇环则该连通分量的任意两点都可以形成奇环。下面有证明 步骤三的证明 1.首先明确若存在奇环则奇环上任意点必存在两条路径可以到达而且长度必为一奇一偶。 2.所以如果再添加一个点或几个的话他们必与此环有联通且存在两条路径。 3.若单看这新添加的这几个点或这一个点他们之间一定存在一条路径把他们连通若该路径为奇数则可以和环上的偶数路径搭配构成奇环。反之若为偶数则可以和环上的奇数路径搭配构成奇环。所以无论如何都可以搭配成奇环。 下面是代码 1 #includeiostream2 #includecstdio3 #includealgorithm4 #includecmath5 #includecstring6 #includevector7 using namespace std;8 9 int gi()10 {11 int str0;12 char chgetchar();13 while(ch9||ch0)chgetchar();14 while(ch0 ch9)strstr*10ch-0,chgetchar();15 return str;16 }17 const int N1001;18 int n,m;19 bool d[N][N];20 int num0;21 struct Lin22 {23 int next,to;24 } a[N*N*2];25 int head[N];26 int ans0;27 int color[N];28 bool c[N];29 30 void init(int x,int y)31 {32 a[num].nexthead[x];33 a[num].toy;34 head[x]num;35 }36 vectorintq[N];37 int dfn[N],low[N],st[N],top0,NUM0,flg[N],bel[N],sum0;38 39 40 void Clear()41 {42 memset(d,0,sizeof(d));43 for(int i1; iN-1; i)44 {45 dfn[i]low[i]flg[i]bel[i]color[i]head[i]st[i]c[i]0;46 q[i].clear();47 }48 numNUMtopanssum0;49 }50 51 void dfs(int x,int last)52 {53 int u,v;54 dfn[x]low[x]NUM;55 flg[x]1;56 st[top]x;57 for(int ihead[x]; i; ia[i].next)58 {59 ua[i].to;60 if(ulast)continue;61 if(!dfn[u])62 {63 dfs(u,x);64 low[x]min(low[x],low[u]);65 if(low[u]dfn[x])66 {67 sum;68 while(top)69 {70 vst[top--];71 flg[v]false;72 bel[v]sum;73 q[sum].push_back(v);74 if(vu)break;75 }76 q[sum].push_back(x);77 }78 }79 else if(flg[u])low[x]min(dfn[u],low[x]);80 }81 }82 83 bool Make(int x)84 {85 int u;86 for(int ihead[x]; i; ia[i].next)87 {88 ua[i].to;89 if(bel[u]!bel[x])continue;90 if(color[u]color[x])return false;91 if(!color[u])92 {93 color[u]3-color[x];94 if(!Make(u))return false;95 }96 }97 return true;98 }99
100 void work()
101 {
102 int x,y;
103 for(int i1; im; i)
104 {
105 xgi();
106 ygi();
107 d[x][y]d[y][x]1;
108 }
109 for(int i1; in; i)
110 for(int ji1; jn; j)
111 if(!d[i][j])init(i,j),init(j,i);
112 for(int i1; in; i)if(!dfn[i])dfs(i,i);
113
114 bool ff1;
115 int size;
116 ans0;
117 for(int i1; isum; i)
118 {
119 if(q[i].size()2)continue;
120 memset(color,0,sizeof(color));
121 color[q[i][0]]1;
122 sizeq[i].size();
123 for(int j0;jsize;j)bel[q[i][j]]i;
124 ffMake(q[i][0]);
125 if(!ff)for(int j0;jsize;j)c[q[i][j]]1;
126 }
127 for(int i1;in;i)if(!c[i])ans;
128 printf(%d\n,ans);
129 }
130
131 int main()
132 {
133 while(1)
134 {
135 ngi();
136 mgi();
137 if(!n !m)break;
138 work();
139 Clear();
140 }
141 return 0;
142 } 转载于:https://www.cnblogs.com/Yuzao/p/6750054.html
