JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (oldest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Round Tables External Competitions Cactus spoj
 Re: Cactus spoj (response to post by isMeta) | Reply The answer won't fit in signed long long, you need to take unsigned long long. Also, if there are no cycle in the graph, the answer would be 1, not 0
 Cactus spoj | Reply http://www.spoj.com/problems/CAC/I am having problems with that problem. My idea is the following: I just find the number of edges in each cycle and afterwards multiply all of them. However, I get a wrong answer each time I submit. Here is the code:```#include #include #include using namespace std;   int n,e;   vector nbs[101]; int height[101]; int par[101]; vector cycles;   void clear() { for (int i = 0; i<100; ++i) { nbs[i].clear(); cycles.clear(); height[i] = 0; par[i] = 0; } }       int dfs(int vertex, int parent) { if (height[vertex] > 0) { if (par[parent]==vertex || height[parent]-height[vertex] <= 0)return 0; return 1+height[parent]-height[vertex]; } height[vertex] = height[parent]+1; par[vertex] = parent; int ans = 0; int sz = nbs[vertex].size(); for (int i = 0; i < sz; ++i) { int val = dfs(nbs[vertex][i], vertex); if (val>0) cycles.push_back(val); } return ans; }   int main() { int t; scanf("%d", &t); for (int k = 1; k <= t; ++k) { scanf("%d%d", &n,&e); clear(); for (int i = 0; i < e; ++i) { int a,b; scanf("%d%d",&a,&b); nbs[a].push_back(b); nbs[b].push_back(a); } dfs(1,0); long long ans = 0; if(cycles.size() > 0) { ans = 1;   for (int i = 0; i < cycles.size(); ++i) { ans*=cycles[i]; } } printf("Case %d: %LLd\n", k, ans); } return 0; } ```
 Forums Round Tables External Competitions Cactus spoj Previous Thread  |  Next Thread