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]);
}
}
12442 - Forwarding Emails
Moderator: Board moderators
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;
}