首页 > 代码库 > 9E-并查集

9E-并查集

给你n个点,这n个点之间有m条边相连,问能不能再添加几条边,使这n个点刚好能围成一个圈

 #include <iostream>#include <vector>#define pii pair <int, int>#define mp make_pairusing namespace std;vector <vector <int> > G;vector <bool> mark;vector <pii> res;bool cycle = 0;void dfs(int u, int p = -1){    mark[u] = 1;    int i;    for (i = 0; i < G[u].size(); i++)    {        if (!mark[G[u][i]])            dfs(G[u][i], u);        else if (G[u][i] != p)            cycle = 1;    }}bool check_res(){    int i;    for (i = 0; i < G.size(); i++)        if (G[i].size() != 2 || !mark[i])            return 0;    return 1;}bool check_good(){    int i;    for (i = 0; i < G.size(); i++)        if (G[i].size() > 2)            return 0;    return 1;}void add(){    int i, j;    for (i = 0; i < G.size(); i++)        for (j = i + 1; j < G.size(); j++)            if (G[i].size() < 2 && G[j].size() < 2)            {                mark.assign(G.size(), 0);                dfs(i);                if (!mark[j])                {                    res.push_back(mp(i, j));                    G[i].push_back(j);                    G[j].push_back(i);                }            }}int main(){    int n, m, i, a, b;    cin >> n >> m;    G.resize(n);    mark.resize(n);    if (n == 1)    {        if (m == 0)            cout << "YES\n1\n1 1\n";        else if (m == 1)            cout << "YES\n0\n";        else            cout << "NO\n";        return 0;    }    for (i = 0; i < m; i++)    {        cin >> a >> b;        if (a == b)        {            cout << "NO" << endl;            return 0;        }        G[a - 1].push_back(b - 1);        G[b - 1].push_back(a - 1);    }    dfs(0);    if (check_res())    {        cout << "YES" << endl;        cout << 0 << endl;    }    else if (check_good() && m <= n && !cycle)    {        cout << "YES" << endl;        add();        cout << res.size() + 1 << endl;        a = -1, b = -1;        for (i = 0; i < res.size(); i++)            cout << res[i].first + 1 << " " << res[i].second + 1 << endl;        for (i = 0; i < G.size(); i++)            if (G[i].size() < 2)            {                if (a == -1)                    a = i;                else                    b = i;            }        cout << a + 1 << " " << b + 1 << endl;    }    else        cout << "NO" << endl;    return 0;}

 

9E-并查集