JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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 <cstdio>
#include <iostream>
#include <vector>
using namespace std;
 
int n,e;
 
vector<int> nbs[101];
int height[101];
int par[101];
vector<int> 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;
}
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
RSS