【BZOJ】3296: [USACO2011 Open] Learning Languages（tarjan）

http://www.lydsy.com/JudgeOnline/problem.php?id=3296
분명히 모든 군 이 교류 할 수 있 는 군 은 강력 한 연결 블록 이다.
그리고 scc 의 수량 을 구하 면 정 답 은 scc - 1 입 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr2(a, b, c) for1(i, 1, b) { for1(j, 1, c) cout << a[i][j]; cout << endl; }

#define printarr1(a, b) for1(i, 1, b) cout << a[i]; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const int N=50005;

int n, m, ihead[N], cnt, FF[N], LL[N], tot, q[N], top, vis[N], scc;

struct ED { int to, next; }e[N*10];

void add(int u, int v) {

	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;

	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;

}

void tarjan(int x) {

	vis[x]=1; FF[x]=LL[x]=++tot;

	q[++top]=x;

	int v;

	for(int i=ihead[x]; i; i=e[i].next) {

		v=e[i].to;

		if(!FF[v]) tarjan(v), LL[x]=min(LL[x], LL[v]);

		else if(vis[v]) LL[x]=min(LL[x], FF[v]);

	}

	if(FF[x]==LL[x]) {

		++scc;

		do {

			v=q[top--];

			vis[v]=0;

		}while(v!=x);

	}

}



int main() {

	read(n); read(m);

	for1(i, 1, n) {

		int t=getint();

		while(t--) {

			int v=getint();

			add(i, n+v);

		}

	}

	for1(i, 1, n) if(!FF[i]) tarjan(i);

	print(scc-1);

	return 0;

}

 
 
 
 
Description
농부 존의 N (2 < = N < = 10, 000) 마리 젖소, 번 호 는 1. N 으로 모두 M (1 < = M < = 30, 000) 가지 언어 를 유창 하 게 사용 하고 번 호 는 1. M., i 머리 에서 K 를 말 할 줄 안다.i (1 < = K i < = M) 종 언어, 즉 Li1, L_i2,..., L_{iK_i} (1 <= L_ij <= M)。 FJ 젖소 가 똑똑 하지 않 아서 Ki 의 총 화 는 많아야 100, 000 이다.소 두 마 리 는 어떤 언어 를 할 줄 알 지 않 는 한 직접 교류 할 수 없다.그러나 공통어 가 없 는 젖소 들 은 다른 소 들 에 게 통역 을 시 킬 수 있다.다시 말 하면 소 A 와 B 는 대 화 를 할 수 있 고 하나의 서열 의 젖소 T 만 존재 한다.1，T_2，...，T_k, A 와 T1. 어떤 언어 를 할 줄 알 아 요. T1 과 T2. 어떤 언어 도 할 줄 알 아 요.......................................................k 와 B 는 어떤 언어 를 할 줄 안다.농부 존 은 그의 젖소 가 더욱 단결 하 기 를 희망 하기 때문에, 그 는 임의의 두 마리 의 소 사이 에서 교류 할 수 있 기 를 희망 한다.그 는 책 을 사서 그의 젖소 에 게 어떤 언어 도 가 르 칠 수 있다.FJ 는 상당히 검소 한 농민 으로서 최소한 의 책 을 사서 모든 젖소 가 서로 말 을 할 수 있 도록 하려 고 한다.그 가 확정 하도록 돕다.    *그 가 구 매해 야 할 책의 최저 수량
Input
* 첫 번 째 줄: 두 개의 빈 칸 으로 구 분 된 정수: N 과 M * 두 번 째 줄: N + 1 줄: i + 1 줄 이 묘사 한 우 i 의 언어, Ki + 1 개의 빈 칸 으로 구 분 된 정수: Ki L_i1         L_i2，...，L_I{K_i}。
Output
* 첫 번 째 줄: 하나의 정수, FJ 가 최소한 구 매해 야 할 책의 개수.

Sample Input
3 3
2 3 2
1 2
1 1
Sample Output
1
HINT
3 번 소 에 게 두 번 째 책 을 사주 면 됩 니 다.
Source
Silver