12442 - Forwarding Emails

[beginer]

please igot WA and itied all testcases i found,all give me right answers,this is my code:
#include<stdio.h>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
#define Max 50100
int dp[Max];
vector< int> visited;
vector< vector< int> > adj;
//int dp[100000];
int dfs(int u)
{
visited = 1;
if (dp != 0)
return dp;
dp = 1;
// int ans = 1;
bool cycle = false;
int x = (int)adj.size();
for (int i = 0; i < x; i++)
{
int k = adj;
if (visited[k] == 1)
cycle = true;
dp += dfs(k);
if (binary_search(adj[k].begin(), adj[k].end(), u))
dp--;

}
if (cycle)
{
dp = 0, visited = 0;
}
visited[u] = 2;
return dp[u];
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int ts;
scanf("%d", &ts);
for (int ct = 1; ct <= ts; ct++)
{
memset(dp, 0, sizeof dp);
scanf("%d", &n);
visited.clear();
visited.assign(n, 0);
adj.assign(n, vector<int>());
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
x--, y--;
adj[x].push_back(y);
}
int ans = -1, pos = 0;
for (int i = 0; i < n; i++)
{

if (!visited)
{

int x = dfs(i);
if (x>ans)
{
pos = i;
ans = x;
}
}
}
printf("Case %d: %d\n", ct, pos + 1);
//printf("%d", dp[2]);
}
}

[punter]

I am getting WA. Can anyone help me out here?

Code: Select all

#include <bits/stdc++.h>
using namespace std;

#define INF_MAX 	2147483647
#define INF_MIN 	-2147483648
#define INF 		(1 << 30)
#define EPS			1e-9
#define PI 			acos(-1.0)
#define N    		2 + 50000
#define MOD			10000000007
#define sz(x) 		(int)(x).size()
#define all(x) 		(x).begin(), (x).end()
#define pb 			push_back
#define mp			make_pair
#define ms(x, a) 	memset((x), (a), sizeof(x))
#define F           first
#define S           second
#define rep(i,a,b)  for(int i=(a); i<(b); i++)
#define repC(i,x) 	for(size_t i=0; i<x.size(); i++)
#define repIT(i,c) 	for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define nn          '\n'

typedef long long 		LL;
typedef pair<int,int> 	pii;
typedef vector<int> 	vi;
typedef vector<string> 	vs;
typedef vector<char>	vc;
typedef vector<bool>    vb;
typedef vector< pii >   vii;
typedef map<string,int> msi;
typedef map<int,int>	mii;
typedef map<char,int>	mci;
typedef map<int,string>	mis;

template<class T> T Abs(T x) {return x>0 ? x : -x;}
template<class T> T Max(T a, T b) { return a>b ? a : b; }
template<class T> T Min(T a, T b) { return a<b ? a : b; }
template<class T> T gcd(T a, T b) { return b ? gcd(b,a%b) : a; }
bool isVowel(char ch){ch=tolower(ch);return(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u');}


int g[N];               // it's a special graph, each node has only one neighbor
int reachability[N];    // reachability[i] -> # of nodes reachable from node i
int d[N];               // discovery time of each node
int timer;				// global variable, will be used to calculate the discovery time of each node
int reaches;            // global variable, will be used to calculate the reachability of each node
int cycle_len;			// global variable, will be used to track the members of a cycle

void dfs(int u)
{
    d[u] = ++timer;

    int v = g[u];
    if(!d[v] and !reachability[v]) { 	// v is the next node in dfs-tree
		dfs(v);
		if(cycle_len > 0) {
			reachability[u] = reaches;
		}
		else {
			reachability[u] = ++reaches;
		}
		--cycle_len;
    }
    else if(reachability[v] == 0) { 	// a cycle detected
		assert(d[u] > d[v]);
		cycle_len = reaches = (d[u] - d[v]) + 1;
		reachability[u] = reaches;
		--cycle_len;
    }
    else { 								// reached at another 'explored' component
		reaches = reachability[v] + 1;
		reachability[u] = reaches++;
    }
}


int main()
{
    	int i, j, k, n, tc;

	cin >> tc;
	rep(cn, 1, tc+1)
	{
        cin >> n;
        rep(k, 0, n)
        {
            cin >> i >> j;
            g[i] = j;
        }

        ms(reachability, 0);
        ms(d, 0);
        timer = reaches = cycle_len = 0;

        rep(i, 1, n+1) if(!d[i])
        {
			dfs(i);
        }

        int ans = 0, best = 0;
        rep(i, 1, n+1)
        {
			if(reachability[i] > best) {
				best = reachability[i];
				ans = i;
			}
        }

        cout << "Case " << cn << ": " << ans << nn;
	}

	return 0;
}