7-12 分而治之 (25 分)

 运用并查集， 先用两个数组，分别存连通的两个点，然后判断是否这两个点至少有一个被攻占，如果没有就合并。最后查一下是否全是孤立的点。

#include 
#include 
using namespace std;
const int N = 10010;
int p[N], ex[N], ey[N];
bool st[N];
int n, m;

int find(int x)
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y)
{
    p[find(x)] = find(y);
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> ex[i] >> ey[i];
    
    int k;
    cin >> k;
    while(k--)
    {
        memset(st, false, sizeof st);
        int x;
        cin >> x;
        for(int i = 1; i <= x; i++)
        {
            int xx;
            cin >> xx;
            st[xx] = true;
        }
        
        for(int i = 1; i <= n; i++) p[i] = i;
        for(int i = 1; i <= m; i++) 
        {
            if(st[ex[i]] || st[ey[i]]) continue;
            merge(ex[i], ey[i]);
        }
        
        int flag = 1;
        for(int i = 1; i <= n; i++)
        {
            if(p[i] != i) 
            {
                flag = 0;
                break;
            }
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}