Page 3 of 3

Re: 12442 - Forwarding Emails

Posted: Mon Apr 11, 2016 2:54 am
by 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]);
}
}