Submission #992991

---

Source Code Expand

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

vector< vector<int> > G;
vector< vector<int> > lang;
int visit[100100];

void dfs(int n){
  visit[n] = 1;
  for(int i = 0;i < (int)G[n].size(); ++i){
    if(!visit[G[n][i]])dfs(G[n][i]);
  }
}

bool is_connect(int n,int m){
  int p1 = 0;
  int p2 = 0;
  while(p1 < (int)lang[n].size()
	&& p2 < (int)lang[m].size()){
    if(lang[n][p1] == lang[m][p2])
      return true;
    if(lang[n][p1] < lang[m][p2])
      ++p1;
    else
      ++p2;
  }
  return false;
}

int main(void){
  int n,m;
  cin >> n >> m;
  G.resize(n);
  lang.resize(n);
  fill(visit,visit+100100,0);
  for(int i = 0;i < n;++i){
    int k;
    cin >> k;
    for(int j = 0;j < k;++j){
      int l;
      cin >> l;
      lang[i].push_back(l);
    }
    sort(lang[i].begin(),
	 lang[i].end());
  }
  for(int i = 0;i < n;++i){
    for(int j = i+1;j < n;++j){
      if(is_connect(i,j)){
	G[i].push_back(j);
	G[j].push_back(i);
      }
    }
  }
  /*
  for(int i = 0;i < n;++i){
    for(int j = 0;j < (int)G[i].size();++j){
      cout << G[i][j] << " ";
    }
    cout << endl;
  }
  */
  dfs(0);
  for(int i = 0;i < n;++i){
    if(!visit[i]){
      puts("NO");
      return 0;
    }
  }
  puts("YES");
  return 0;
}

Submission Info

Judge Result