社区讨论

求大佬给看看,只有50分,第9个点还re了

P1330封锁阳光大学参与者 6已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mi6m3k11
此快照首次捕获于
2025/11/20 07:06
4 个月前
此快照最后确认于
2025/11/20 07:06
4 个月前
查看原帖
CPP
#include<iostream>
#include<algorithm>
using namespace std;
struct line
{
    int next;
    int to;
}edge[1000000];
int tot;
int g[100000];
int n, m;
int ans[3];
void add(int a, int b)
{
    tot++;
    edge[tot].to = b;
    edge[tot].next = g[a];
    g[a] = tot;
}
bool flag = true;
int color[100000];
void dfs(int a, int c)
{
    color[a] = c;
    ans[c + 1]++;
    int temp = g[a];
    while (temp != 0)
    {
        int x = edge[temp].to;
        if (color[x] == c) { flag = false;return; }
        if (color[x] == 0)
        {
            dfs(x, -c);
        }
        temp = edge[temp].next;
    }
    return ;
}
int main()
{
    int ans1 = 0;
    cin >> n >> m;
    for (int i = 0;i < m;i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    for (int i = 1;i <= tot;i++)
    {
        if (color[i] == 0)
        {
            ans[0] = 0;
            ans[2] = 0;
            dfs(i, 1);
            ans1 += min(ans[0], ans[2]);
        }
    }
    if (!flag)cout << "Impossible";
    else
    {
        cout << ans1;
    }
    return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...