Doubt in today's ABC 226 Problem E

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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!

Комментарии (4)

Показать архивные | Написать комментарий?

Koful123

3 года назад, # |

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

→ Ответить

your.nemesis

3 года назад, # ^ |

← 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

Блог пользователя 51stDimension