The Accomodation of Students

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
int match[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool dfs(int u, int c) {
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i]) {

        int j = e[i];

        if (!color[j]) {
            if (!dfs(j, 3 - c))
                return false;
        } else if (color[j] == c)
            return false;
    }

    return true;
}

bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {

        int j = e[i];

        if (!st[j]) {
            st[j] = true;

            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(color, 0, sizeof color);
        memset(h, -1, sizeof h);
        idx = 0;

        while (m -- ) {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }

        bool flag = true;

        for (int i = 1; i <= n; i ++ )

            if (!color[i]) {
                if (!dfs(i, 1)) {
                    flag = false;
                    break;
                }
            }

        if (!flag)
            puts("No");
        else {
            memset(match, 0, sizeof match);
            int res = 0;

            for (int i = 1; i <= n; i ++ ) {

                memset(st, false, sizeof st);

                if (find(i))
                    res ++ ;
            }

            printf("%d\n", res / 2);
        }
    }

    return 0;
}

Courses

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310, M = 30010;

int n, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool find(int x) {
    for (int i = h[x]; i != -1; i = ne[i]) {

        int j = e[i];

        if (!st[j]) {
            st[j] = true;

            if (match[j] == 0 || find(match[j])) {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        memset(match, 0, sizeof match);
        memset(h, -1, sizeof h);
        idx = 0;
        scanf("%d%d", &m, &n);

        for (int i = 1; i <= m; i ++ ) {

            int k;
            scanf("%d", &k);

            while (k -- ) {
                int a;
                scanf("%d", &a);
                add(i, a);
            }
        }

        if (n < m) {
            puts("NO");
            continue;
        }

        int res = 0;

        for (int i = 1; i <= m; i ++ ) {

            memset(st, false, sizeof st);

            if (find(i))
                res ++ ;
        }

        if (res == m)
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

Fire Net

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30;

int n;
int match[N];
bool st[N];
char mp[N][N];
int x[N][N], y[N][N];
bool g[N][N];
int cnt_x, cnt_y;

bool find(int u) {
    for (int i = 0; i < cnt_y; i ++ )

        if (g[u][i])
            if (!st[i]) {
                st[i] = true;

                if (match[i] == 0 || find(match[i])) {
                    match[i] = u;
                    return true;
                }
            }

    return false;
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;

        for (int i = 0; i < n; i ++ )

            scanf("%s", mp[i]);
        memset(match, 0, sizeof match);
        memset(g, false, sizeof g);

        cnt_x = 1;

        for (int i = 0; i < n; i ++ ) {

            for (int j = 0; j < n; j ++ ) {

                if (mp[i][j] == '.')
                    x[i][j] = cnt_x;
                else if (mp[i][j] == 'X')
                    cnt_x ++ ;
            }

            cnt_x ++ ;
        }

        cnt_y = 1;

        for (int i = 0; i < n; i ++ ) {

            for (int j = 0; j < n; j ++ ) {

                if (mp[j][i] == '.')
                    y[j][i] = cnt_y;
                else if (mp[j][i] == 'X')
                    cnt_y ++ ;
            }

            cnt_y ++ ;
        }

        for (int i = 0; i < n; i ++ )

            for (int j = 0; j < n; j ++ )

                if (mp[i][j] == '.')
                    g[x[i][j]][y[i][j]] = true;
        int res = 0;

        for (int i = 0; i < cnt_x; i ++ ) {

            memset(st, false, sizeof st);

            if (find(i))
                res ++ ;
        }

        printf("%d\n", res);
    }

    return 0;
}