## 12442 - Forwarding Emails

All about problems in Volume 124. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

beginer
New poster
Posts: 2
Joined: Sat Apr 09, 2016 12:34 pm

### Re: 12442 - Forwarding Emails

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);
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);
for (int i = 1; i <= n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
x--, 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
New poster
Posts: 2
Joined: Thu Aug 04, 2016 8:16 am

### Re: 12442 - Forwarding Emails

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;
}
``````