2020-2021:teams:namespace:牛客多校第三场

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:namespace:牛客多校第三场 [2020/07/20 09:47]
great_designer [A]
+++ 2020-2021:teams:namespace:牛客多校第三场 [2020/07/23 21:28] (当前版本)
great_designer [A]
@@ 行 466: / 行 466: @@
 </hidden>
-=====A=====
+=====G=====
+以下是补题。
 <hidden>
-<code C>
+<code C++>
-</code>
+#include<stdio.h>
-</hidden>
+#include<stdlib.h>
+#include<vector>
-=====A=====
+using namespace std;
-<hidden>
+struct head
-<code C>
+{
+	struct head *r;
+	int val;
+};
+int dsu[1000000];
+int get(int v)
+{
+	if (v == dsu[v]) return v;
+	else return dsu[v] = get(dsu[v]);
+}
+pair<struct head*, struct head*> g[1000000];
+pair<struct head *, struct head *> merge(pair <struct head *, struct head *> a, pair <struct head *, struct head *> b)
+{
+	if (!a.second) return b;
+	else
+	{
+		a.second->r = b.first;
+		return make_pair(a.first, b.second);
+	}
+}
+pair <struct head*, struct head*> lst(int x)
+{
+	struct head *t =(struct head*)malloc(sizeof(struct head));
+	t->r=0;
+	t->val=x;
+	return make_pair(t,t);
+}
+int main()
+{
+	int t;
+	scanf("%d",&t);
+	while(t--)
+	{
+		int n,m;
+		scanf("%d%d",&n,&m);
+		int i;
+		for(i = 0; i < n; i++)
+		{
+			dsu[i] = i;
+			g[i] =make_pair((struct head*)0,(struct head*)0);
+		}
+		for(i = 0; i < m; i++)
+		{
+			int x, y;
+			scanf("%d%d",&x,&y);
+			g[x] = merge(g[x], lst(y));
+			g[y] = merge(g[y], lst(x));
+		}
+		int q;
+		scanf("%d",&q);
+		for(i = 0; i < q; i++)
+		{
+			int c;
+			scanf("%d",&c);
+			if (get(c) != c)
+			{
+				continue;
+			}
+			else
+			{
+				vector<int> ord;
+				struct head *s;
+				for(s = g[c].first; s != 0; s = s->r)
+				{
+					int z = s->val;
+					if (get(z) != c)
+					{
+						int who = get(z);
+						dsu[who] = c;
+						ord.push_back(who);
+					}
+				}
+				g[c] =make_pair((struct head*)0,(struct head*)0);
+				vector<int>::iterator p;
+				for(p=ord.begin();p!=ord.end();p++)
+				{
+					g[c] = merge(g[c],g[(*p)]);
+				}
+			}
+		}
+		for(i = 0; i < n; i++)
+		{
+			printf("%d ",get(i));
+		}
+		printf("\n");
+	}
+}
 </code>
 </hidden>

2020-2021/teams/namespace/牛客多校第三场.1595209633.txt.gz · 最后更改: 2020/07/20 09:47 由 great_designer