舒阳 的博客

舒阳 的博客

QAQ QWQ

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

posted on 2019-09-03 17:53:31 | under 题解 |

A New Idea

提供一种新的思路,把每个语言和每只牛看成一个点。
如果某只牛会说这种语言,就让这个牛代表的节点向这个语言代表的节点连一条双向边。
然后判断图有几个连通块即可
连通块之间连边就相当于这条边的某一个牛需要一本书学语言。
我们可以知道如果有$n$个联通块,那么只需要$n - 1$条边就能使整个图联通。

code

/*!
 * 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;
}