10004 - Bicoloring

#include <bits/stdc++.h>
#define  pb     push_back
#define  MAX    10000007
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

bool BFS(int s);

vector<int>graph[300];
queue<int>Q;
bool mark[300];
map<int,string>mp;

int main()
{

    int n;
  //  read;
 //   write;
    while(~scanf("%d",&n))
    {
        if(n==0) break;
        int edge;
        scanf("%d",&edge);
        memset(mark,false,sizeof(mark));
        mp.clear();
        for(int i=0; i<300; i++) graph[i].clear();
        int start;
        for(int i=0; i<edge; i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            start=a;
            graph[a].pb(b);
            graph[b].pb(a);

        }
        while(!Q.empty()) Q.pop();
        if( BFS(start)==true) puts("BICOLORABLE.");
        else puts("NOT BICOLORABLE.");

    }


    return 0;
}

bool BFS(int start)
{
    Q.push(start);
    mp[start]="black";
   // int cnt=0;

    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        mark[node]=true;
        int len=graph[node].size();
        for(int i=0; i<len; i++)
        {
            int n=graph[node][i];

            if(mark[n]==false)
            {
                Q.push(n);

                if(mp[node]=="black") mp[n]="red";
                else mp[n]="black";
            }
            else
            {
                if(mp[node]==mp[n]) return false;

            }

        }

    }
    return true;

}

BYTESE2 - The Great Ball solution

#include <bits/stdc++.h>
#define  pb     push_back
#define  MAX    10000007
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct node
{
    int start,last;
} ary[1000];
bool cmp( node i,node j)
{
    if(i.last==j.last)
    {
        return i.start<j.start;
    }
    else return i.last<j.last;
}

int main()
{
   // read;
    //  write;
    int test;
    scanf("%d",&test);
    while(test--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d %d",&ary[i].start,&ary[i].last);
        }
        sort(ary,ary+n,cmp);
        int ans=0;
       // for(int i=0; i<n; i++) printf("%d %d\n",ary[i].start,ary[i].last);

        for(int i=0; i<n; i++)
        {
            int cnt=0;
            for(int j=0; j<n; j++)
            {
                if( (ary[j].start<=ary[i].last)&&(ary[j].last>=ary[i].last)) cnt++;
            }
            ans=max(ans,cnt);
        }

        printf("%d\n",ans);


    }

    return 0;
}