题解 P3026 【[USACO11OPEN]学习语言Learning Languages】

ShuYuMo

2019-09-03 17:53:31

Solution

# A New Idea 提供一种新的思路,把每个语言和每只牛看成一个点。 如果某只牛会说这种语言,就让这个牛代表的节点向这个语言代表的节点连一条双向边。 然后判断图有几个连通块即可 连通块之间连边就相当于这条边的某一个牛需要一本书学语言。 我们可以知道如果有$n$个联通块,那么只需要$n - 1$条边就能使整个图联通。 # code ```cpp /*! * FileName: luogu-3026.cpp * This Problem is on luogu. The ID of the problem is 3026. * Copyright(c) 2019 Shu_Yu_Mo * MIT Licensed * Luogu: https://www.luogu.org/space/show?uid=44615 * Github: https://github.com/oldsuold/ * Gitee: https://gitee.com/Shu_Yu_Mo/ * These words were created by an amazing tool on 2019-09-03 17:07:16 written by Shu_Yu_Mo. */ #include<cstdio> #include<cstring> #include<cmath> #include<cstring> #include<iostream> #include<cmath> #include<vector> #include<queue> #include<algorithm> #define inf 0x7fffffff using namespace std; const int _N = 11000; const int _M = 31000; inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; } int n, m; int head[_N + _M]; struct edges{ int node; int nxt; }edge[1100000]; int tot = 0; void add(int u, int v) { edge[++tot].nxt = head[u]; head[u] = tot; edge[tot].node = v; } bool vis[_N + _M]; void dfs(int now) { vis[now] = true; for(register int i = head[now];i;i = edge[i].nxt) { int exNode = edge[i].node; if(vis[exNode]) continue; dfs(exNode); } } int main() { n = read(), m = read(); for(register int i = 1;i <= n;i++) { int k = read(); for(register int j = 1;j <= k;j++) { int tmp = read(); add(i, n + tmp); add(n + tmp, i); } } int ans = 0 ; memset(vis, false, sizeof(vis)); for(register int i = 1;i <= n;i++) if(!vis[i]) { dfs(i); ans ++; } printf("%d", ans - 1); return 0; } ```