Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define F(i, n) for (int i = 0; i < n; i++)
- using namespace std;
- int n, m;
- bool a[100 * 100 * 10 + 2];
- // map<int, vector<int>> tre;
- vector<int> tre[1000*100+5];
- void doIT(int i)
- {
- for (auto x : tre[i])
- if (!a[x])
- {
- doIT(x);
- a[x] = true;
- }
- // if (!a[i])
- // {
- // for (auto x : tre[i])
- // doIT(x);
- // a[i] = 1;
- // }
- }
- void solve()
- {
- cin >> n >> m;
- int t = m;
- for (int i = 0; i <= n; i++)
- a[i] = false;
- while (t--)
- {
- int a, b;
- cin >> a >> b;
- if (tre[a].size() < 1)
- {
- tre[a] = {b};
- }
- else
- {
- tre[a].push_back(b);
- }
- // if (tre[b].size() < 1)
- // {
- // tre[b] = {a};
- // }
- // else
- // {
- // tre[b].push_back(a);
- // }
- }
- int count = 0;
- // for(auto i: tre){
- // for(auto x:i.second){
- // cout<<i.first<<" ** "<<x<<" ";
- // }
- // cout<<"|\n#\n";
- // }
- for (int i = 1; i <= n; i++)
- {
- if (!a[i])
- {
- doIT(i);
- ++count;
- // a[i]=1;
- }
- }
- // for (int i = 1; i <= n; i++)
- // {
- // cout << a[i] << " ";
- // }
- // cout << "\nanser is :- ";
- cout << count - 1;
- }
- int main()
- {
- int t = 1;
- // cin>>t;
- while (t--)
- {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement