C++17

爱O2不O2

#include <iostream>
#include <algorithm>
#include <array>
#include <cstdlib>
#include <vector>
using namespace std;

static const int SIZE = 100005;

template<int size>
class DFSType
{
    array<int, size> c;
    array<int, 3> cnt;
    array<vector<int>, size> *g;
    bool flag;
    void dfs(int u);
public:
    DFSType(array<vector<int>, size> &g);
    int operator() (int u);
};

template<int size>
DFSType<size>::DFSType(array<vector<int>, size> &g)
{
    this->g = &g;
    flag = false;
    cnt[1] = 1;
    cnt[2] = 0;
}

template<int size>
void DFSType<size>::dfs(int u)
{
    for(int j=0; j<(*g)[u].size(); ++j)
    {
        int v = (*g)[u][j];
        if(!c[v])
        {
            c[v] = 3-c[u];
            ++cnt[c[v]];
            dfs(v);
        }
        else if(c[u] == c[v])
        {
            flag = true;
        }
        else
        {
            continue;
        }
    }
}

template<int size>
int DFSType<size>::operator() (int u)
{
    if(c[u])
    {
        c[u] = 1;
        dfs(u);
        if(flag)
        {
            return min(cnt[1], cnt[2]);
        }
        return -1;
    }
    return -2;
}

int main()
{
    int n, m, ans = 0;
    bool flag = true;
    array<vector<int>, SIZE> g;
    cin >> n >> m;
    for(int i=1; i<=m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    DFSType<SIZE> dfs(g);
    for(int i=1; i<=n; ++i)
    {
        int x = dfs(i);
        if(x == -2)
        {
            continue;
        }
        if(x == -1)
        {
            flag = false;
            break;
        }
        ans += x;
    }
    if(flag)
    {
        cout << ans << endl;
    }
    else
    {
        cout << "Impossible" << endl;
    }
    return EXIT_SUCCESS;
}