图不连通！

Wmkf3 @ 2024-05-11 20:36:09

by Terrible @ 2024-05-11 20:49:28

你是说题目给出的有向图不是弱连通的吗？

经过本人测试：

#include<cstdio>
#include<set>
int f[10001];
int find(int p){return f[p]==p?p:f[p]=find(f[p]);}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)f[i]=i;
    while(m--)
    {
        int u,v;scanf("%d%d",&u,&v);
        f[find(v)]=find(u);
    }
    std::set<int> s;
    for(int i=1;i<=n;i++)s.insert(find(i));
    return 3*(s.size()!=1);
}

得到记录，记录中没有返回 3 的 RE 测试结果，也就说明题目给定的有向图都是弱连通的。

本题给出非强连通的有向图是合情合理的;单向连通的情况在文中并未被提及，也不是关键点。