codeforces (Good Bye 2014) question B

B. New Year Permutation

standard solution

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

typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

#define rep(i,n) for(int (i)=(0);(i)<(n);(i)++)
#define rep1(i,n) for(int (i)=(1);(i)<=(n);(i)++)
#define fr(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define mp make_pair
#define pb push_back
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define db(x) cerr << #x << " : " << x << endl;
#define pv(c,a,b) cerr << "{ "; fr(i,a,b) cerr<<c[i]<<", "; cerr << "}" << endl;
#define fill(a,v) memset(a,v,sizeof(a))

const int inf = (int) 1e9;
const int maxn = (int) 1e5 + 10;

int n,a[maxn],comp,vis[maxn];
char s[maxn];
vector<int> g[maxn];

void dfs(int x){
    vis[x]=comp;
    rep(i,g[x].size()){
        int y=g[x][i];
        if(!vis[y]){
            dfs(y);
        }
    }
}

int main() {
    scanf("%d",&n);
    rep(i,n) scanf("%d",&a[i]);
    rep(i,n){
        scanf("%s",s);
        rep(j,n){
            if(s[j]=='1'){
                g[i].pb(j);
            }
        }
    }
    comp=1;
    rep(i,n) if(!vis[i]){
        dfs(i);
        comp++;
    }
    rep(i,n) fr(j,i+1,n) if(vis[i]==vis[j] && a[i]>a[j]) swap(a[i],a[j]);
    rep(i,n) {
        if(i+1!=n)printf("%d ",a[i]);
        else printf("%d\n",a[i]);
    }
    return 0;
}

my mistake 

most imp point its not just the connected nodes where exchanges can be made but which node belong to the same tree there exchanges can be made , like in graph A-B-C so exchange can of course be made bet A and  B , B- C but a direct exchange can also be made bet A-C. .something similar to floyd warshall , but yes dat cannot be applies because different forests exist in the graph.

hack was 

3
3 1 2
001
001
110

my output was 2 1 3 bcz if we dont consider that above situation we would never be able to perform a exchange between 1st and 2nd (positions) so the value 1 will never come to 1st place

but if we look at the above solution a exchange can be made bcz 1st and position belong to same forest via 3rd position