SPOJ GOSSIPER

This problem fooled me into thinking that it was all about transitive closure. So the first thing I did was to use Floyd-Warshall on it which failed miserably. But then with the help of Gowtham I could figure out that a meeting does not propagate the gossip back to the previous gossiper, a fact that I had clearly ignored even when it was screaming out in the sample input. Anyways couple of WAs, TLEs and SIGSEGVs later I finally got an AC. Phew...

#include<stdio.h>

#include<string>

#include<map>

#include<iostream>

using namespace std;

char tab[2100][2100];

map<string,int> name_map;




int main() {

int n,m;

while(scanf("%d%d",&n,&m)!=EOF) {

if(n==0 && m==0) return 0;

int _n=0,x,y;

string name1,name2;

name_map.clear();

while(_n<n) {

cin>>name1;

name_map.insert(make_pair(name1,_n++));

}

while(m--) {

cin>>name1>>name2;

x=name_map.find(name1)->second;

y=name_map.find(name2)->second;

for(_n=0;_n<n;++_n) {

if(tab[x][_n] && _n!=y) tab[y][_n]=1;

if(tab[y][_n] && _n!=x) tab[x][_n]=1;

}

tab[x][y]=tab[y][x]=1;

}

int cnt=0;

for(x=0;x<n;++x) {

for(y=0;y<n;++y) {

if(tab[x][y]) {

cnt++;

tab[x][y]=0;

}




}

}

if(cnt==n*n-n) printf("YES\n");

else printf("NO\n");

}

return 0;

}