LightOJ 1003 Solution

Drunk Solution

#include<bits/stdc++.h>

#define mx 10100

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int ind[mx], color[mx];

vector<int>a[mx];

map<string, int>mp;

int min_node(int node)

{

    int p = 0;

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

    {

        if(ind[i] == 0 && color[i] == 0)

        {

            p = i;

            break;

        }

    }

    return p;

}

void clears()

{

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

        ind[i] = 0, color[i] = 0, a[i].clear();

    mp.clear();

}

int main()

{

    fast

    int t, k = 1;

    cin >> t;

    while(t--)

    {

        int n, node = 0;

        string x, y;

        cin >> n;

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

        {

            cin >> x >> y;

            if(mp[x] == 0)

            {

                node++;

                mp[x] = node;

            }

            if(mp[y] == 0)

            {

                node++;

                mp[y] = node;

            }

            a[mp[x]].push_back(mp[y]);

            ind[mp[y]]++;

        }

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

        {

            int x = min_node(node);

            for(auto j : a[x])

            {

                if(color[j] == 0 && ind[j] > 0)

                    ind[j]--;

            }

            color[x] = 1;

        }

        bool flag = true;

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

        {

            if(ind[i] > 0)

            {

                flag = false;

                break;

            }

        }

        cout << "Case " << k++ << ": ";

        if(flag == true)

            cout << "Yes" << "\n";

        else

            cout << "No" << "\n";

        clears();

    }

    return 0;

}