1012 - Guilty Prince - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
using namespace std;

int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    int Edgdes;
    cin >> Edgdes;
    vector<int>adj[20000+1];
    int color[20000+1];
    memset(color,GRAY,sizeof color);
    for(int i=0; i<Edgdes; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int mx = 0;
    for(int i=0; i<20000+1; i++){
        if((adj[i].size()!=0) && (color[i] == GRAY)){
            int  black=0,white=0;
            queue<int>q;
            q.push(i);
            color[i] = BLACK;
            black++;
            while(!q.empty()){
                int front = q.front();
                q.pop();
                for(int j=0; j<adj[front].size(); j++){
                    if(color[adj[front][j]] == GRAY){
                       
                        if(color[front] == BLACK){
                            color[adj[front][j]] = WHITE;
                            white++;
                        }else if(color[front] == WHITE){
                            color[adj[front][j]] = BLACK;
                            black++;
                        }
                      
                        q.push(adj[front][j]);
                    }
                }
            }
            mx += max(black,white);
        }
    }
    cout <<Case<<mx<<newl;
   }
    return 0;
}

1238 - Power Puff Girls - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
#define imax INT_MAX
#define max3(a,b,c) max(a,max(b,c))
using namespace std;
string grid[21];
int xd[]={-1,0,1,0};
int yd[]={0,1,0,-1};
bool visited[21][21];
int dist[21][21];
int row , col;
int bfs(int i, int j){
    pair<int,int>p;
    queue<pair<int,int> >q;
    int mx = 0;
   for(int i=0; i<21; i++){
        for(int j=0; j<21; j++)dist[i][j]=imax;
    }
    p = {i,j};
    q.push(p);
    dist[i][j] = 0;
    visited[i][j] = true;
    while(!q.empty()){
        pair<int,int>pt;
        pt = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int x = pt.first;
            int y = pt.second;
            if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && grid[x+xd[i]][y+yd[i]] == 'h'){
                  dist[x+xd[i]][y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                  mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                  return mx;
               
            }else{
                 if((x+xd[i]>=0 && x+xd[i]<row) && (y+yd[i]>=0 && y+yd[i]<col) && (grid[x+xd[i]][y+yd[i]] == '.' ||grid[x+xd[i]][y+yd[i]] == 'a'||grid[x+xd[i]][y+yd[i]] == 'b'||grid[x+xd[i]][y+yd[i]] == 'c' ) && !visited[x+xd[i]][y+yd[i]]){
                    dist[x+xd[i]][ y+yd[i]] = min(dist[x][y]+1, dist[x+xd[i]][y+yd[i]]);
                    mx = max(mx, dist[x+xd[i]][ y+yd[i]]);
                    visited[x+xd[i]][y+yd[i]] = true;
                    q.push({x+xd[i],y+yd[i]});
                }
            }
        }
    }
    return mx;
}
int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    cin >> row >> col;
    for(int i=0; i<row; i++){
        cin >> grid[i];
    }
    int a,b,c;
    for(int i=0; i<row; i++){
        for(int j=0; j<col; j++){
            if(grid[i][j] == 'a'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                a = bfs(i,j);
            }
            if(grid[i][j] == 'b'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                b = bfs(i,j);
            }
            if(grid[i][j] == 'c'){
                memset(visited,0,sizeof visited);
                memset(dist,0,sizeof dist);
                c = bfs(i,j);
            }
        }
    }
        cout<<Case<<max3(a,b,c)<<newl;
   }
    return 0;
}

1009 - Back to Underworld - LOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
#define Case "Case "<<++kase<<": "
#define GRAY 0
#define WHITE 1
#define BLACK 2
using namespace std;

int main()
{
   int T,kase=0;
   cin >> T;
   while(T--){
    int Edgdes;
    cin >> Edgdes;
    vector<int>adj[20000+1];
    int color[20000+1];
    memset(color,GRAY,sizeof color);
    for(int i=0; i<Edgdes; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int mx = 0;
    for(int i=0; i<20000+1; i++){
        if((adj[i].size()!=0) && (color[i] == GRAY)){
            int  black=0,white=0;
            queue<int>q;
            q.push(i);
            color[i] = BLACK;
            black++;
            while(!q.empty()){
                int front = q.front();
                q.pop();
                for(int j=0; j<adj[front].size(); j++){
                    if(color[adj[front][j]] == GRAY){
                        //cout<<front<<' '<<adj[front][j]<<newl;
                        if(color[front] == BLACK){
                            color[adj[front][j]] = WHITE;
                            white++;
                        }else if(color[front] == WHITE){
                            color[adj[front][j]] = BLACK;
                            black++;
                        }
                       // cout<<black<<' '<<white<<newl;
                        q.push(adj[front][j]);
                    }
                }
            }
            mx += max(black,white);
        }
    }
    cout <<Case<<mx<<newl;
   }
    return 0;
}

1003 - Drunk - LightOJ

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define newl '\n'
#define FAST ios_base::sync_with_stdio(0);
using namespace std;
map<string , int>visited;
map<string, vector<string> >mp;
bool cycle;

void visit(string start){
  visited[start] = GRAY;
  for(int i=0; i<mp[start].size(); i++){
    if(visited[mp[start][i]] == WHITE){
      visit(mp[start][i]);
    }else if(visited[mp[start][i]] == GRAY){
      cycle = true;
      return;
    }
  }
  visited[start] = BLACK;
}

void DFS(){
  map<string, vector<string> >::iterator it;
  visited.clear();
  for(it = mp.begin() ; it!=mp.end(); it++){
    if(cycle)return;
    if(visited[(*it).first] == WHITE){
      visit((*it).first);
    }
  }
}
int main()
{
    FAST;
    int t , kase=0;
    cin >> t;
    while(t--){
      int n;
      cin >> n;
      for(int i=0; i<n; i++){
        string a , b;
        cin >> a >> b;
        mp[a].push_back(b);
        visited[a] = WHITE;
      }
      cycle = false;
      DFS();
      if(cycle)cout<<"Case "<<++kase<<": No"<<newl;
      else cout<<"Case "<<++kase<<": Yes"<<newl;
      mp.clear();
      visited.clear();
    } 

    return 0;
}