[sicily] 1021. Couples

淩亂°似流年 2022-07-24 04:16 149阅读 0赞

1021. Couples
    
    Constraints
    Time Limit: 1 secs, Memory Limit: 32 MB
    
    
    Description
    
    N couples are standing in a circle, numbered consecutively clockwise from 1 to 2N. Husband and wife do not always stand together. We remove the couples who stand together until the circle is empty or we can't remove a couple any more.
    
    Can we remove all the couples out of the circle?
    
    Input
    
    There may be several test cases in the input file. In each case, the first line is an integer N(1 <= N <= 100000)----the number of couples. In the following N lines, each line contains two integers ---- the numbers of each couple.
    N = 0 indicates the end of the input.
    
    Output
    
    Output "Yes" if we can remove all the couples out of the circle. Otherwise, output "No".
    
    Sample Input
    
    4
    1 4
    2 3
    5 6
    7 8
    
    2
    1 3
    2 4
    
    0
    Sample Output
    
    Yes
    No

#include<iostream>
    #include<stack>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin >> n;
    
    
        while(n != 0)
        {
            int a,b;
            int couple[2*n+1];
    
            for (int i = 1; i <= n; ++i)
            {
                cin >> a >> b;
                couple[a] = couple[b] =  i;
            }
    
            stack<int> s;
            for (int i = 1; i <= 2*n; ++i)
            {
                if(!s.empty() && s.top() == couple[i])
                    s.pop();
                else
                    s.push(couple[i]);
            }
            if(s.empty())
                cout << "Yes" << endl;
            else
                cout << "No" << endl;
            cin >> n;
        }
        return 0;
    }