Setter : Ujjawal Gupta
Tester : Prashant Singh
Editorial : Apoorv Dixit
Difficulty:
Medium
Prerequisite:
Graph, DFS
Explanation & Algorithm:
Find number of nodes in each connected components in graph , then print the maximum number of nodes in a component.
Time Complexity:
O(V+U)
Space Complexity :
O(V+U)
Solution:
Setter's Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dfs(ll cur, vector<vector> &graph, vector &vis){
vis[cur] = true;
ll ans = 1;
for(auto x: graph[cur]){
if(!vis[x]){
ans += dfs(x, graph, vis);
}
}
return ans;
}
ll fun(ll n, ll m, vector<vector> &arr){
vector vis(n, false);
ll ans = 0;
vector<vector> graph(n);
for(auto x:arr){
graph[x[0]].push_back(x[1]);
graph[x[1]].push_back(x[0]);
}
for(ll i=0;i<n;i++){
if(!vis[i]){
ans = max(ans, dfs(i, graph, vis));
}
}
cout<<ans<<endl;
}
void solve()
{
ll n,m;
cin>>n>>m;
vector<vector> arr(m, vector(2));
for(int i=0;i<m;i++){
ll a,b;
cin>>a>>b;
a–;b–;
arr[i][0] = a;
arr[i][1] = b;
}
}
int main()
{
ll t;
cin >> t;
while (t–)
{
solve();
}
return 0;
}