CactusCount.cpp

#include <bits/stdc++.h>
#define all(x)    x.begin(), x.end()
#define allr(x)   x.rbegin(), x.rend()
#define sz(x)     ((int)x.size())
#define ln(x)     ((int)x.length())
#define mp        make_pair
#define pb        push_back
#define ff        first
#define ss        second
#define endl      '\n'
#define dbg(x)    cout << #x << ": " << x << endl;
#define clr(x,v)  memset(x, v, sizeof(x));
#define fix(x)    cout << setprecision(x) << fixed;
#define FASTIO    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

using ll = long long int;
using ld = long double;
using pi = pair<int, int>;

const double PI = acos(-1.0);
const double eps = 1e-9;
const ll mod = 1e9 + 7;
const int inf = 1e7;
const int MAXN = 200 + 5;

class CactusCount
{
public:
    int countCacti(int, vector <string>);
};

int parent[MAXN], sz[MAXN];
void make_set(int n)
{
    iota(parent, parent + n, 0);
    fill(sz, sz + n, 1);
}
int find_set(int v)
{
    if(v == parent[v])
        return v;
    else
        return parent[v] = find_set(parent[v]);
}
bool union_set(int a, int b)
{
    a = find_set(a), b = find_set(b);
    if(sz[a] < sz[b])
        swap(a, b);
    if(a != b)
        parent[b] = a, sz[a] += sz[b];
    return a != b;
}


int CactusCount::countCacti(int n, vector <string> edges)
{
    int u, v;
    string E;
    for(string &x : edges) E += x;
    for(char &x : E) if(x == ',') x = ' ';
    stringstream ss(E);

    vector<vector<int>> adj(n);
    make_set(n);
    while(ss >> u >> v) adj[u - 1].pb(v - 1), adj[v - 1].pb(u - 1), union_set(u - 1, v - 1);

    vector<bool> valid(n, true), vis(n);

    int cnt = 0;
    function<void(int, int, int)> dfs = [&](int start, int u, int prev)
    {
        vis[u] = 1;
        for(int v : adj[u])
        {
            if(v == prev) continue;
            if(!vis[v]) dfs(start, v, u);
            else if(v == start) cnt++;
        }
    };

    for(int i = 0; i < n; i++)
    {
        cnt = 0;
        vis.assign(n, false);
        dfs(i, i, i);
        if(cnt > 1) valid[find_set(i)] = false;
    }

    int ans = 0;
    for(int i = 0; i < n; i++)
        if(i == find_set(i))
            ans += valid[i];
    return ans;
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, int p0, vector <string> p1, bool hasAnswer, int p2)
{
    cout << "Test " << testNum << ": [" << p0 << "," << "{";
    for (int i = 0; int(p1.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << "\"" << p1[i] << "\"";
    }
    cout << "}";
    cout << "]" << endl;
    CactusCount *obj;
    int answer;
    obj = new CactusCount();
    clock_t startTime = clock();
    answer = obj->countCacti(p0, p1);
    clock_t endTime = clock();
    delete obj;
    bool res;
    res = true;
    cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
    if (hasAnswer)
    {
        cout << "Desired answer:" << endl;
        cout << "\t" << p2 << endl;
    }
    cout << "Your answer:" << endl;
    cout << "\t" << answer << endl;
    if (hasAnswer)
    {
        res = answer == p2;
    }
    if (!res)
    {
        cout << "DOESN'T MATCH!!!!" << endl;
    }
    else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2)
    {
        cout << "FAIL the timeout" << endl;
        res = false;
    }
    else if (hasAnswer)
    {
        cout << "Match :-)" << endl;
    }
    else
    {
        cout << "OK, but is it right?" << endl;
    }
    cout << "" << endl;
    return res;
}
int main()
{
    bool all_right;
    all_right = true;

    int p0;
    vector <string> p1;
    int p2;

    {
        // ----- test 0 -----
        p0 = 3;
        string t1[] = {"1 2,1 3,2 3"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 1;
        all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 1 -----
        p0 = 10;
        p1.clear() /*{}*/;
        p2 = 10;
        all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 2 -----
        p0 = 5;
        string t1[] = {"1 2,3 4,4 5"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 2;
        all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 3 -----
        p0 = 17;
        string t1[] = {"1 2,2 3,3 4,4 5,5 3,1 3,6 7,7 8,6 8,8 9,9 1", "0,10 11,11 9,12 13,14 15,15 16,16 17,14 17,14 16"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 2;
        all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
        // ------------------
    }

    if (all_right)
    {
        cout << "You're a stud (at least on the example cases)!" << endl;
    }
    else
    {
        cout << "Some of the test cases had errors." << endl;
    }
    return 0;
}
// END KAWIGIEDIT TESTING



//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!