5 8
2 3
1 2
2 5
1 4
1 5
3 4
3 4
4 4
8
7 6 8 2 3 4 5 1
> 1 1 1 1 2 3 4 5

Instead of doing the cuts in the order given in the input,
I found it easier to do it in reverse order, so we get merging instead of cutting.

Edited by author 29.03.2023 21:05

5 7
1 2
2 3
1 4
4 5
1 5
2 5
4 3
4
3 4 7 2

ans: 1 1 2 3

use dsu

I use Disjoint-set
who can help me?

Can someone help how to make C# code faster?
Here is my code:

using System;
using System.Collections.Generic;
class Program
    {
        static int countCut(List<int>[] nods, List<int> uncheckedNodes)
        {
            int next = 0;
            int count = 0;
            do
            {
                count++;
                watchCut(nods, uncheckedNodes, next);
                if (uncheckedNodes.Count > 0)
                    next = uncheckedNodes[0];
                else
                    next = -1;
            } while (next != -1);
            return count;
        }
        static void watchCut(List<int>[] nods, List<int> uncheckedNodes, int node)
        {
            uncheckedNodes.Remove(node);
            for (int i = 0; i < nods[node].Count; i++)
            {
                if (uncheckedNodes.Contains(nods[node][i]))
                    watchCut(nods, uncheckedNodes, nods[node][i]);
            }
        }
        static void Main(string[] args)
        {
            string[] inp_NM = Console.ReadLine().Split(' ');
            int N, M;
            N = Convert.ToInt32(inp_NM[0]);
            M = Convert.ToInt32(inp_NM[1]);
            int[,] threads = new int[M, 2];
            List<int>[] nods = new List<int>[N];
            for (int i = 0; i < N; i++) nods[i] = new List<int>();
            for (int i = 0; i < M; i++)
            {
                string[] inp_thread = Console.ReadLine().Split(' ');
                threads[i, 0] = Convert.ToInt32(inp_thread[0]) - 1;
                threads[i, 1] = Convert.ToInt32(inp_thread[1]) - 1;
                    nods[threads[i, 0]].Add(threads[i, 1]);
                    nods[threads[i, 1]].Add(threads[i, 0]);
            }
            int Q;
            Q = Convert.ToInt32(Console.ReadLine());
            int[] cuts = new int[Q];
            string[] inp_tear = Console.ReadLine().Split(' ');
            for (int i = 0; i < Q; i++)
            {
                cuts[i] = Convert.ToInt32(inp_tear[i]) - 1;
            }
            for (int i = 0; i < Q; i++)
            {
                    nods[threads[cuts[i], 0]].Remove(threads[cuts[i], 1]);
                    nods[threads[cuts[i], 1]].Remove(threads[cuts[i], 0]);
                List<int> uncheckedNodes = new List<int>();
                for (int l = 0; l < N; l++) uncheckedNodes.Add(l);
                Console.Write(countCut(nods, uncheckedNodes)+" ");
            }

        }
    }

Edited by author 24.11.2020 08:00

There can be multiple edges. For instance:
1 2
2 1

Using a set will give WA. Try multi-set or some other data structure in c++.

Edited by author 07.09.2020 15:22

Edited by author 07.09.2020 15:22

hm.ok



Edited by author 25.08.2020 03:14

I used DSU and I have WA16. Can you help me?

#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[100003],b[100003],c[100003];
vector<pair<int,int> >v;
vector<int>g[100003];
bool vis[100003];
int qq[100003];
map<int,int>mp;
void dfs(int x,int cc){
    vis[x]=1;
    for(int i=0;i<g[x].size();i++)
        if(!vis[g[x][i]])
            dfs(g[x][i],cc);
    qq[x]=cc;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>a[i]>>b[i],
        a[i]--,
        b[i]--;
    cin>>q;
    for(int i=0;i<q;i++)cin>>c[i],c[i]--,v.push_back(make_pair(a[c[i]],b[c[i]])),a[c[i]]=b[c[i]]=-1;
    reverse(c,c+n);reverse(v.begin(),v.end());
    for(int i=0;i<m;i++)
        if(a[i]!=-1)
            g[a[i]].push_back(b[i]),
            g[b[i]].push_back(a[i]);
    int cnt=0;
    for(int i=0;i<n;i++)
        if(!vis[i])
            mp[cnt]=cnt,
            dfs(i,cnt++);
    vector<int>ans;
    for(int i=0;i<q;i++){
        ans.push_back(cnt);
        if(mp[qq[v[i].first]]!=mp[qq[v[i].second]])
            mp[qq[v[i].first]]=mp[qq[v[i].second]],
            qq[v[i].first]=qq[v[i].second],
            cnt--;
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<' ';
}

unable to understand first example. can anyone please kindly  explain.

gimme test, please)

If its not a multy eadge and it is a bridge, then it increase the number of pieces by one otherwise the pieces amount left same. Am I right?

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define pq priority_queue
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << endl
#define ALL(a) (a.begin()),(a.end())
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORI(a,b) for(int i = a; i<b; i++)
#define fastio ios::sync_with_stdio(0); cin.tie(NULL);
const int INF = 0x3f3f3f3f;


struct ar{
    ll x,y;
};


ar v[100100];
int p[100100] = {0};
ll id[100100];
ll sz[100100];
ll num;

ll find(ll x){
    if(id[x] == x) return x;
    return id[x] = find(id[x]);
}

void join(ll x, ll y){
    ll p = find(x);
    ll q = find(y);
    if(p==q) return;
    num--;
    if(sz[p] > sz[q]) {
        ll t = q; p = q; q = t;
    }
    id[p] = q;
    sz[p] += sz[q];
}




    int main(){
        fastio
        ll n,m,i,q;
        cin >> n >> m;
        num = n;

        ll arf[100100];
        ll ans[100100];



        FOR(i,m){
            cin >> v[i+1].x >> v[i+1].y;
        }
        FOR(i,m+1){
            id[i+1] = i+1;
            sz[i+1] = 1;
        }
        cin >> q;
        FOR(i,q){
            ll x;
            cin >> x;
            p[x] = 1;
            arf[q-i] = x;
        }

        FOR(i,m+1){
            if(i==0) continue;
            if(!p[i]){
                join(v[i].x, v[i].y);
            }
        }

        ans[q] = num;
        for(int i = 1; i<=q; i++){
            join(v[arf[i]].x, v[arf[i]].y);

            ans[q-i] = num;

        }

        for(int i = 1; i<=q; i++){
            cout << ans[i] << " ";
        }



        cout << "\n";


        return 0;
    }











Edited by author 17.03.2019 04:30

GOOD peoples Please help me! I have got WA#5! I used DSU!! My program gives right answer for all my tests! But again WA#5 and I can not found my mistake! I shall wait advices or tests! Thank you advance!!!

Learn something aboutDSU(disjoint-set-union

http://e-maxx.ru/algo/dsu

Edited by author 07.03.2013 23:32

I am not allocating any memory in heap, everything is defined globally, why do I get Memory Limit Exceeded error on test 5? Why this error is not given for test 1? I'm not even using STL.

It also happened to me solving another problem(1220. Stacks), I got memory limit exceeded on test 10, same situation as here. Does IO operations use memory? I assume I get this error as test-cases get larger in size... (I also tried disabling IO buffering)

Can there be identical threads in the test?
Like:
4 4
1 2
1 2
2 3
3 4
3
1 2 3
And if they can occur is the answer 2 2 3 or 1 2 3?

I solve this problem with C++ first and got WA#6, but I can't find where is my problem, so I rewrite it with C# with the same solution, but to my surprise, this time I got AC.
And even till now I don't know what are the differences between my two lovely code.
Any idea?
//Sorry for my poor English

I don't think there are such threads as (2 Edges)
 1 2
 2 1

And although my program can solve that case, I still WA on test5. Can you help me and give me some advice? Thank you very much!