Doubt in today's ABC 226 Problem E

According to the Editoral

The answer is supposed to be

Let K be = Number of components such the number of edges == number of vertices then the answer is pow(2,k)

I used the same method but I calculated the number of cycles in each connected component. Le var be a variable. And if the cyclecount in a connected component is == 1 then I do var++ and later on the ans = pow(2,var)

I am getting 6 WA.

My Code

ll cycleCount;

void dfs(vector<ll> adj[],ll curr,ll par,vector<bool>& visited){
    visited[curr] = true;
    for(auto u:adj[curr]){
        if(!visited[u]){
            dfs(adj,u,curr,visited);
        }
        else if(u!=par){
            cycleCount++;
        }
    }
}

void solve(ll tc){
    ll n,m;
    cin>>n>>m;

    vector<ll> adj[n+1];

    for(ll i=0;i<m;i++){
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }

    vector<bool> visited(n+1,false);

    ll k  = 0;

    for(ll i=1;i<=n;i++){
        if(!visited[i]){

            cycleCount = 0;

            dfs(adj,i,-1,visited);

            cycleCount = cycleCount/2;

            debug(cycleCount);

            if(cycleCount!=1){
                continue;
            }

            k++;
        }
    }   

    if(k==0){
        cout<<0<<endl;
        return;
    }   

    ll ans = modExpo(2,k);
    ans  =  ans%mod;

    cout<<ans<<endl;
}

There is a possibility that my cycleCount function is wrong. If thats the case please do let me know!

Thank you!

Comments (4)

Show archived | Write comment?

Koful123

5 years ago, hide # |

In circle graph your code prints 0 but it should be 2

→ Reply

your.nemesis

5 years ago, hide # ^ |

← Rev. 2 →

4 4

1 2

2 3

3 4

1 4

For this input my code is printing 2.

If a component does not have same number of edges and nodes answer should be 0. Did it make sense?

vipbaswan

The issue is that your logic has a very little flaw.

Suppose a graph has 2 connected components. One component has a cycle, while another component has 0 cycles. Answer should be 0 in that case (because there is no way to direct edges of the second component), while your logic would still say 2.

EDIT: Try this test case: 7 6 1 2 2 3 3 4 5 6 6 7 5 7

#	User	Rating
1	Benq	3792
2	Kevin114514	3678
3	VivaciousAubergine	3647
4	jiangly	3582
5	strapple	3515
6	tourist	3473
7	Radewoosh	3418
8	Um_nik	3376
9	maroonrk	3361
10	turmax	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

51stDimension's blog