OJ Board

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 60000;
vector<int> answers;
int parent[MAXN];
int child[MAXN];
int potential[MAXN];
bool visited[MAXN];
bool inCycle[MAXN];
int DFS(int root)
{
    if(root == -1) return 0;
    if(potential[root] != -1) return potential[root];
    if(visited[root])
    {
        inCycle[root] = true;
        return 0;
    }
    visited[root] = true;
    potential[root] = 1 + DFS(child[root]);
    if(inCycle[root])
    {
        int currentNode = child[root];
        while(currentNode != root)
        {
            potential[currentNode] = potential[root];
            currentNode = child[currentNode];
        }
    }
    return potential[root];
}
void read()
{
    memset(parent, -1, sizeof parent);
    memset(child, -1, sizeof child);
    memset(potential, -1, sizeof potential);
    memset(visited, 0, sizeof visited);
    memset(inCycle, 0, sizeof inCycle);
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i)
    {
        int from, to;
        cin >> from >> to;
        parent[to] = from;
        child[from] = to;
    }
    int maxPotential = 0;
    int node = 0;
    for(int i = 1; i <= N; ++i)
    {
        if(!visited[i])
        {
            DFS(i);
        }
        if(maxPotential < potential[i])
        {
            maxPotential = potential[i];
            node = i;
        }
    }
    answers.push_back(node);
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for(int i = 0; i < T; ++i)
    {
        read();
    }
    for(int i = 0; i < T; ++i)
    {
        cout<<"Case "<<i+1<<": "<<answers[i];
        if(i < T-1) cout<<'\n';
    }
    return 0;
}

Code: Select all

#include<iostream>
#include<cstdio>
#include<vector>
#define MAX 50010

using namespace std;
int nVertex;
int *visited,time;
vector<vector<int> >adjList(MAX);



int DFS_VIST(int n)
{
    time=time+1;
    int v;
    visited[n]=1;
    for(int i=0;i<adjList[n].size();i++) {
        v=adjList[n][i];
        if(visited[v]==0) {
            DFS_VIST(v);
            //cout<<"time="<<time<<"  ";
        }
    }
    return time;
}

int DFS(int n) {
    visited=new int[nVertex+1];
    time=0;
    for(int i=1;i<=nVertex;i++) visited[i]=0;
    return DFS_VIST(n);

}

int main()
{

    int t,x,y,c=1;
    cin>>t;
    while(t--)
    {
        cin>>nVertex;
        for(int i=0;i<=nVertex;i++) adjList[i].clear();
        for(int i=1;i<=nVertex;i++) {
            cin>>x>>y;
            adjList[x].push_back(y);
        }
        int maximum=0,t,solution=0;
        for(int i=1;i<=nVertex;i++){
            t=DFS(i);
            if(maximum<t) {
                maximum=t;
                solution=i;
            }

        }
        cout<<"Case "<<c<<": "<<solution<<endl;
        c++;
    }
   return 0;

}

Code: Select all

 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
#include <climits>
#include <list>
#include <string>
using namespace std;

/*------- Constants---- */
#define MX 50004
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)

/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))


/*------ template functions ------ */
template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}

int touch[MX], arr[MX], dp[MX];

vector<int> tmp;
int endVal;
int flag = 0;
int before;
int why = 0;

void call ( int n , int cnt)
{
	
	if(touch[n]== 1) {
		endVal = n;
		flag = 1;
		return ;
	}
	if( dp[n] !=-1) return;
	else {
		
		touch[n] = 1;
		
		if( dp[arr[n]] != -1)  {
			before = cnt + dp[arr[n]] + 1;
			
			return;
		}
		
		call(arr[n] , cnt+1);
		if(  flag ) tmp.push_back(n);
		
		
		if( endVal == n ) {
			flag = 0;
			before = cnt  + (int )(tmp.size());
		}
	}
	return;
}
int main()
{
	
	
	int test , n, i , maximum , a, b , cs  =0 ,messe;
	//freopen("in.txt", "r", stdin);
	cin >> test ;
	
	while (test --) {
		cin >> n ;
		ms(dp, -1);
		ms(touch, 0);
		for( int i = 0 ; i < n ; i++ ){
			cin >> a >> b;
			
			arr[a] = b;
			if( a == b ) {
				dp[a] = 1;
				//printf("Wrong Input\n");
			}
		}
		maximum = 0 ;
		for( int i = 1; i <= n ; i ++){
			
			if( dp[i] ==-1) {
				call(i , 0 );
				dp[i] = before;
				
			}
			for (int j = 0; j < tmp.size(); j ++ ) {
				if(dp[tmp[j]]==-1)  dp[tmp[j]] =( int)  tmp.size();
			}
			if( dp[i] > maximum){
				maximum = dp[i];
				messe = i;
			}
			tmp.clear();
		
		}
		
		printf("Case %d: %d\n",++cs, messe);
	}
	return 0;
}

Code: Select all

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
#include <queue>
#include<string>
#include<cstring>
#include<sstream>
#include<list>
#include<math.h>
#include<map>
#include<set>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define PB push_back
#define PI acos(-1.0)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))

#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)

#define LL long long
#define MOD 1000000007
#define MX 100010

#define pii pair<int,int>
int fx[]={1,-1,0,0,1,1,-1,-1}; 
int fy[]={0,0,1,-1,1,-1,1,-1};


char cell[105][105]; 
int d[105][105],vis[105][105];
int row,col;

int check(int tx,int ty)
{

	if(tx>=0 && tx<row && ty>=0 && ty<col)
		return 1;

	return 0;
}
struct graph{
	int x;
	int y;
};
//vector<int>G[5];//graph adjacency list
int g[50005];
int sum[50005];
//graph G[50005];
int visited[50005]={0};
vector<int>vc;
int bfs(int n,int src){
	queue<int>Q;
	int total =0,u;
	Q.push(src);
	int v;
	visited[src]=1;
	sum[src]=1;
	while(!Q.empty())
	{
		u = Q.front();
		{
			v = g[u];//adjacent node
			if(!visited[v] && v)
			{
				vc.push_back(v);
				visited[v] =1;
				sum[v]=sum[u]+1;
				Q.push(v);
			}
			else //already visited
			{
				//if(v==0)
				//	return sum[u];
				if (v == src)
					return sum[u]+1;
				return sum[u]+sum[v];//sum[src]+sum[v]
			}
		}
		Q.pop();
	}
	//return sum[v];
}
int main() 
{

	int n,m,x,y,i,j,k;
	int no_of_prior[102],no_dependency,index_of_dependent;

	char ch,second[1000],first[1000];
	string str;
	int test_case=0;
	int number;
	/*freopen ("d:/input.txt","w",stdout);
	for(i=1;i<50000;i++)
	{
		printf("%d %d\n",i,i+1);
	}*/
	scanf("%d",&test_case);
	for(k=1;k<=test_case;k++)
	{
		scanf("%d",&n);
		vc.clear();
		memset(sum,0,sizeof(sum));
		memset(visited,0,sizeof(visited));
		memset(g,0,sizeof(g));
		i=0;
		while(i<n)
		{
			scanf("%d%d",&x,&y);
			g[x] =y;
			i++;
		}
		
		int ans =1;
		int max =-1;
		for(i=1;i<=n;i++)
		{
			if(visited[i]==0 && g[i])
			{
				sum[i] = bfs(n,i);
				if(sum[i]>=max)
				{
					max = sum[i];
					ans =i;
					/*if(max == n)
						break;*/
				}
				for(j=0;j<vc.size();j++)
				sum[vc[j]] = sum[i];
				vc.clear();
			}
		}
		
		printf("Case %d: %d\n",k,ans);

	}
	return 0;
}

Code: Select all

import java.util.Arrays;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Miles Stevenson
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task12442 solver = new Task12442();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task12442 {
    int G[] = new int[50000], depth[] = new int[50000], visited[] = new int[50000];
    int T, maxDepth, maxDepthNode;

    public int dfs(int u) {
        int v = G[u];
        int r = 0;
        visited[u] = 1;
        if (visited[v] == 0)
            r = dfs(v) + 1;
        visited[u] = 0;
        depth[u] = r;
        return r;
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        T = in.nextInt();

        // iterate each test case
        for (int testCase = 0; testCase < T; testCase++) {
            int totalNodes = in.nextInt();
            maxDepth = 0;
            Arrays.fill(G, 0);
            Arrays.fill(visited, 0);
            Arrays.fill(depth, -1);

            // populate adjacency graph
            for (int i = 0; i < totalNodes; i++) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                G[u] = v;
            }

            // iterate over each vertex with a dfs call
            for (int i = 0; i < totalNodes; i++) {
                if (depth[i] == -1)
                    dfs(i);
                if (depth[i] > maxDepth) {
                    maxDepth = depth[i];
                    maxDepthNode = i;
                }
                else if (depth[i] == maxDepth && i < maxDepthNode)
                    maxDepthNode = i;
            }

            // print final data for test case
            out.println("Case " + (testCase+1) + ": " + (maxDepthNode+1));
        }
    }
}

class InputReader {
    private BufferedReader reader;
    private StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String nextLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        } catch (NullPointerException e) {
            return null;
        }
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

Code: Select all

1
7
2 4
4 1
1 3
3 4
5 3
6 2
7 4

Code: Select all

6

Code: Select all

for (int i = 0; i < totalNodes; i++) {
                if (depth[i] == -1)
                    dfs(i);
                if (depth[i] > maxDepth) {
                    maxDepth = depth[i];
                    maxDepthNode = i;
                }
                else if (depth[i] == maxDepth && i < maxDepthNode)
                    maxDepthNode = i;
            }

Code: Select all

Scanner sc = new Scanner(System.in);
int numCases = sc.nextInt();

for (int i = 1; i <= numCases; i++) {
	int numNodes = sc.nextInt(), src, dst;
	
	for (int i = 0; i < numNodes; i++) {
		src = sc.nextInt();
		dst = sc.nextInt();
		//process the edge [src, dst]
	}
	//process
	System.out.println("Case " + i + ": " + yourSolutionHere);
}
sc.close();