647_div2_500.cpp

#include <iostream>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

class Fragile2{
    public:
    	int isSafe(vector<vector<int> > &M, int row, int col, vector<vector<bool> > &visited){
            int N = M[0].size();
    		return (row >= 0) && (row < N) &&    
           			(col >= 0) && (col < N) && 
           			(M[row][col] && !visited[row][col]);
		}

		void DFS(vector<vector<int> > &M, int row, int col, vector<vector<bool> > &visited) {
    		static int rowNbr[] = {-1, -1, -1,  0, 0,  1, 1, 1};
    		static int colNbr[] = {-1,  0,  1, -1, 1, -1, 0, 1};
    		visited[row][col] = true;
    		for (int k = 0; k < 8; ++k){
        		if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited) )
            		DFS(M, row + rowNbr[k], col + colNbr[k], visited);
			}
		}
 
		int connected(vector<vector<int> > &M){
            		int N = M[0].size();
    		vector<vector<bool> > visited(N, vector<bool>(N, false));
    		int count = 0;
    		for (int i = 0; i < N; ++i)
        		for (int j = 0; j < N; ++j)
            		if (M[i][j] && !visited[i][j]) {                          
               			 DFS(M, i, j, visited);     
                		 ++count;                 
            		}
    		return count;
		}
    
    	int countPairs(vector <string> graph){
            int N = graph[0].size();
            vector<vector<int> > g(N, vector<int>(N));
            for(int i=0; i<graph.size(); i++){
                for(int j=0;j<graph[i].size(); j++){
                   	if(i == j) g[i][j] = 1;
			else {
				if(graph[i][j] == 'N') g[i][j] = 0;
				else g[i][j] = 1;
			}
                }
            }
           
            int main_cnt = connected(g);
            
	    cout << main_cnt << endl;       
     
            int result = 0;
            for(int i=0; i<N; i++){
                for(int j=i+1; j<N; j++){
			vector<vector<int> > temp(N, vector<int>(N));
			for(int k=0;k<N;k++){
				for(int l=0;l<N;l++){
					temp[k][l] = g[k][l];
				}
			}

			for(int k=0; k<N; k++){
				temp[i][k] = 0;
				temp[j][k] = 0;
			}

			for(int k=0; k<N; k++){
				temp[k][i] = 0;
				temp[k][j] = 0;
			}
			
			int temp_res = connected(temp);	
			cout << temp_res << endl;
			temp_res = temp_res - 2;
		// this is the bitch. If i rmeove two vertices, i need to take care of them too. temp_res = temp_res - 2 actually	
                    if(main_cnt < temp_res) result = result + 1;
                }
            }
            
            return result;
        }
 };
            
            
int main(){
	int n;
	cin >> n;
	vector<string> g;
	for(int i=0; i<n; i++){
		string str;
		cin >> str;
		g.push_back(str);
	}
	Fragile2 f;
	cout << f.countPairs(g) << endl;
	return 0;
}