Petrozavodsk Winter-2014. U of Latvia Contest B. Doors
题目大意
若干个门上一共有 $n$ 个锁，Scrooge 每天会去按同样顺序把所有他想锁的门锁上。每个门上可能有不止一个锁，那么这些锁的顺序不一定是固定的。但是不同门上一定是按顺序锁的。现在给你若干个上锁序列，问最多能有多少个门。
题目分析
由题意可知，所有的序列中，所有 $x$ 即出现 $y$ 前面又出现在 $y$ 后面，那么说明 $x$ 和 $y$ 一定是在同一个门上。那么如果将所有相邻的点之间建立一条有向边，那么所有在同一个强连通分量中的点都属于同一个门。使用 $Tarjan$ 求解即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, k;
vector <int> e[maxn];
int dfn[maxn];
int low[maxn];
bool vis[maxn];
stack <int> s;
int cnt = 0;
int ans = 0;
int ccnt = 0;
vector <int> vec[maxn];
int dfs(int x){
int y;
vis[x] = true;
s.push(x);
dfn[x] = low[x] = ++cnt;
for(auto y : e[x]){
if(!dfn[y]){
dfs(y);
low[x] = min(low[x], low[y]);
}else if(vis[y]){
low[x] = min(low[x], low[y]);
}
}
if(dfn[x] == low[x]){
ccnt++;
vec[ccnt].push_back(x);
vis[x] = false;
while(s.top() != x){
vec[ccnt].push_back(s.top());
vis[s.top()] = false;
s.pop();
}
s.pop();
}
return 0;
}
int main(){
int i, j;
int x, y;
scanf("%d%d", &m, &n);
for(i=1;i<=m;i++){
scanf("%d", &k);
scanf("%d", &y);
for(j=2;j<=k;j++){
scanf("%d", &x);
e[x].push_back(y);
y = x;
}
}
for(i=1;i<=n;i++){
if(!dfn[i]){
dfs(i);
}
}
printf("%d\n", ccnt);
for(i=1;i<=ccnt;i++){
printf("%d", (int)vec[i].size());
for(auto j : vec[i]){
printf(" %d", j);
}
printf("\n");
}
return 0;
}