Solution to LightOj Problems

LightOj 1009 :Back To Underworld

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;


int color[20005],c,numberOfNode,visited[20005]={0},toBeCalled[20005]={0},local_max;
void bfs(int src_node);
vector<int>graph[20005];
int main()
{

    int edge,i,j,x,y,src,T;
    cin>>T;
    for(int tt=1;tt<=T;tt++)
    {
        int biggestNode=0;
        memset(graph,0,sizeof(graph));//cout<<graph[1][0];
        memset(toBeCalled,0,sizeof(toBeCalled));

        memset(color,0,sizeof(color));
        memset(visited,0,sizeof(visited));
        cin>>edge;
    for(i=1;i<=edge;i++)
    {
        cin>>x>>y;
        if(x>biggestNode)
            biggestNode=x;

        if(y>biggestNode)
            biggestNode=y;

        graph[x].push_back(y);
        graph[y].push_back(x);

        toBeCalled[x]=1;    toBeCalled[y]=1;
    }
    int max_community=0;
    for(int r=1;r<=biggestNode;r++)
    {
        if(toBeCalled[r]==1)
        {
            if(visited[r]==0)
            {
                bfs(r);//cout<<r<<endl;
                max_community+=local_max;//       cout<<local_max<<endl;       //local max is the max number of fighter for each disconnected Graph
            }
        }
    }

        cout<<"Case "<<tt<<": "<<max_community<<endl;
    }
    return 0;
}

void bfs(int src_node)
{
    queue<int>Qu;
    int i,j;c=0;
    numberOfNode=1;
    Qu.push(src_node);
    color[src_node]=0;
    visited[src_node]=1;

    int lykan=0,vampire=1;

    while(!Qu.empty())
    {
        int u=Qu.front();
        Qu.pop();
        for(i=0;i<graph[u].size();i++)
        {
            int v=graph[u][i];
            if(visited[v]==0)
            {
                numberOfNode++;
                if(color[u]==0)
                    {
                        color[v]=1;
                        lykan++;
                    }
                else
                    {
                        color[v]=0;
                        vampire++;
                    }//cout<<u<<"->"<<v<<endl;
                visited[v]=1;
                Qu.push(v);
            }
        }
       }

       if(lykan>vampire)
            local_max=lykan;
       else
            local_max=vampire;
}

LightOj 1111 :Best Picnic Ever

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;

vector<int>road[1005];
int ii;
vector<int>reachable,latestReachable;
int visited[1005];

void dfs(int src)
{
    //cout<<"src="<<src<<endl;
    visited[src]=1;
    if(ii==0)
    {
        reachable.push_back(src);
        latestReachable=reachable;
    }
    else
    {
        for(int l=0;l<reachable.size();l++)
        {
            if(src==reachable[l])
                latestReachable.push_back(src);
        }

    }
 

    for(int i=0;i<road[src].size();i++)
    {
        int u=road[src][i];
        if(visited[u]==0)
        dfs(u);
    }

}
int main()

{
    int u,v,T,K,N,M,k[105];
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        memset(k,0,sizeof(k));
        memset(road,0,sizeof(road));
        cin>>K>>N>>M;
        for(int j=0;j<K;j++)
        {
            cin>>k[j];
        }

        for(int j=0;j<M;j++)
        {
            cin>>u>>v;
            road[u].push_back(v);
        }

        for(ii=0;ii<K;ii++)
        {
            memset(visited,0,sizeof(visited));
            dfs(k[ii]);
            reachable=latestReachable;
            latestReachable.clear();
            /*cout<<k[ii]<<" -> ";
            for(int y=0;y<reachable.size();y++)
                cout<<reachable[y]<<"  ";
            cout<<endl;*/
        }
        cout<<"Case "<<i<<": "<<reachable.size()<<endl;
        reachable.clear();
    }
    return 0;
}