Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- #define int ll
- #define all int i=0; i<n; i++
- #define pb push_back
- #define pf push_front
- #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
- int n;
- vector< pair<int, int> >v;
- map<pair<int, int> , int> cult;
- map<pair<int, int> , int> vertex;
- map<int, pair<int, int> >inv;
- vector<int>g[100005];
- int visit[100005];
- int ans = 0;
- int k = 0;
- void dfs(int source){
- visit[source] = 1;
- int x = inv[source].first; int y = inv[source]. second;
- if(cult[{x+1, y}] == 0)k++;
- if(cult[{x, y+1}] == 0)k++;
- if(cult[{x, y-1}] == 0)k++;
- if(cult[{x-1, y}] == 0)k++;
- for(int j=0; j<g[source].size(); j++){
- if(visit[g[source][j]]==0){
- dfs(g[source][j]);
- }
- }
- }
- int32_t main()
- {
- FAST_IO;
- int r,c,n;
- cin>>r>>c>>n;
- int a,b;
- for(int i=0; i<n; i++){
- visit[i] = 0;
- cin>>a>>b;
- cult[{a-1, b-1}] = 1;
- vertex[{a-1, b-1}] = i;
- inv[i] = {a-1, b-1};
- v.pb({a-1, b-1});
- }
- for(int i=0; i<n; i++){
- int x = v[i].first;
- int y = v[i].second;
- if(cult[{x+1, y}] == 1)g[vertex[{x,y}]].pb(vertex[{x+1, y}]);
- if(cult[{x, y+1}] == 1)g[vertex[{x,y}]].pb(vertex[{x, y+1}]);
- if(cult[{x, y-1}] == 1)g[vertex[{x,y}]].pb(vertex[{x, y-1}]);
- if(cult[{x-1, y}] == 1)g[vertex[{x,y}]].pb(vertex[{x-1, y}]);
- }
- for(int i=0; i<n; i++){
- if(visit[i]==0){
- //cout<<"dfs initiated at source"<<" "<<i<<endl;
- k=0;
- dfs(i);
- }
- ans = max(k, ans);
- }
- cout<<ans<<endl;
- }
Add Comment
Please, Sign In to add comment