S+ 图的连通性与2-sat
注：以下题目均在洛谷上有同名原题
A. 校园网 Network of Schools
这道题写过，强连通块模板题：
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e5+10;
int n,idx,cnt,dfn[N],siz[N],low[N],vis[N],in[N],out[N];
stack<int> s;
vector<int> g[N];
void tarjan(int x){
dfn[x]=low[x]=++idx;
s.push(x);
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!vis[y]) low[x]=min(low[x],low[y]);
}
if(dfn[x]==low[x]){
cnt++;
while(1){
int y=s.top();
s.pop();
vis[y]=cnt;
//siz[cnt]++;
if(y==x) break;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int v;
while(1){
cin>>v;
if(v==0) break;
g[i].push_back(v);
}
}
for(int i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
for(int j=0;j<g[i].size();j++){
if(vis[i]!=vis[g[i][j]]){
in[vis[g[i][j]]]++;
out[vis[i]]++;
}
}
}
if(cnt==1){
cout<<1<<endl<<0<<endl;
return 0;
}
int a,b;
a=b=0;
for(int i=1;i<=cnt;i++){
if(in[i]==0) a++;
if(out[i]==0) b++;
}
cout<<a<<endl;
cout<<max(a,b)<<endl;
return 0;
}B. Going from u to v or from v to u?
写的时候卡了一会…(
其实是挺简单的。Tarjan 缩点，缩完之后拓扑排序，看是否为一条链，链满足题目条件。
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e3+10;
int n,m,cnt,idx,dfn[N],low[N],vis[N],in[N],out[N];
vector<int> g[N],ng[N];
stack<int> s;
void tarjan(int x) {
dfn[x]=low[x]=++idx;
s.push(x);
for (int i=0;i<g[x].size();i++) {
int y=g[x][i];
if (!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (!vis[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]) {
cnt++;
while (1) {
int y=s.top();
s.pop();
vis[y]=cnt;
if (y==x) break;
}
}
}
bool topo() {
queue<int> q;
for (int i=1;i<=cnt;i++) {
if (in[i]==0) q.push(i);
}
int vist=0;
while (q.size()) {
if (q.size()>1) return 0;
int u=q.front();
q.pop();
vist++;
for (int i=0;i<ng[u].size();i++) {
int v=ng[u][i];
in[v]--;
if (in[v]==0) q.push(v);
}
}
return vist==cnt;
}
signed main(){
int T;
cin>>T;
while(T--) {
cin>>n>>m;
cnt=0;
idx=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(vis,0,sizeof vis);
memset(in,0,sizeof in);
memset(out,0,sizeof out);
for (int i=1;i<=n;i++) g[i].clear(),ng[i].clear();
while (s.size()) s.pop();
for (int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for (int i=1;i<=n;i++) {
if (!dfn[i]) tarjan(i);
for (int j=0;j<g[i].size();j++) {
if (vis[i]!=vis[g[i][j]]) {
ng[vis[i]].push_back(vis[g[i][j]]);
in[vis[g[i][j]]]++;
out[vis[i]]++;
}
}
}
int in0=0,out0=0;
for (int i=1;i<=cnt;i++) {
if (in[i]==0) in0++;
if (out[i]==0) out0++;
}
if (in0<=1&&out0<=1&&topo()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}C. 自行车道 Bike paths
其实也是挺简单的（
Tarjan缩点建图，可以发现，因为每个 $\text{SCC}$ 中的点都可以互相到达，所以只需要看新图中这个 $\text{SCC}$ 可以到哪些 $\text{SCC}$ ，加上它们的大小即可。也可以说，对于 $1\le i\le cnt$，
$$
dp_i=\sum dp_j (j\in G_i)
$$
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=5e4+10;
int n,m,cnt,idx,dfn[N],low[N],vis[N],siz[N],dfsp[N];
vector<int> g[N],ng[N];
stack<int> s;
void tarjan(int x) {
dfn[x]=low[x]=++idx;
s.push(x);
for (int i=0;i<g[x].size();i++) {
int y=g[x][i];
if (!dfn[y]) {
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if (!vis[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]) {
cnt++;
while (1) {
int y=s.top();
s.pop();
siz[cnt]++;
vis[y]=cnt;
if (y==x) break;
}
}
}
void dfs(int u) {
if (dfsp[u]) return;
dfsp[u]=siz[u];
for (int v:ng[u]) {
dfs(v);
dfsp[u]+=dfsp[v];
}
}
signed main(){
Cios;
cin>>n>>m;
for (int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
for (int i=1;i<=n;i++) {
if (!dfn[i]) tarjan(i);
for (int j:g[i]) {
if (vis[i]!=vis[j]) ng[vis[i]].push_back(vis[j]);
}
}
for (int i=1;i<=cnt;i++) {
if (!dfsp[i]) dfs(i);
}
for (int i=1;i<=n;i++) cout<<dfsp[vis[i]]-1<<endl;
return 0;
}D. 稳定婚姻
(狗血题目
分析一下题面：一对婚姻被称为Unsafe时，证明这一对婚姻存在于一个环中。存图方式比较关键，我们可以将婚姻边存 男->女，情侣边存 女->男，Tarjan 求强连通分量即可。若这对婚姻存在于一个强连通分量中则为 Unsafe，否则为 Safe
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=24005;
map<string,int> sto;
vector<int> g[N],ng[N];
vector<int> scc[N*2];
vector<pair<int,int>> mr;
stack<int> s;
int n,m,cnt,idx,hn,dfn[N],low[N],vis[N];
void tarjan(int u) {
dfn[u]=low[u]=++idx;
s.push(u);
for (int v:g[u]) {
if (!dfn[v]) {
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if (!vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u]) {
hn++;
while (1) {
int v=s.top();
s.pop();
vis[v]=hn;
scc[hn].push_back(v);
if (v==u) break;
}
}
}
signed main(){
Cios;
cin>>n;
for (int i=1;i<=n;i++) {
string u,v;
cin>>u>>v;
if (!sto[u]) sto[u]=++cnt;
if (!sto[v]) sto[v]=++cnt;
g[sto[u]].push_back(sto[v]);
mr.push_back(make_pair(sto[u],sto[v]));
}
cin>>m;
for (int i=1;i<=m;i++) {
string u,v;
cin>>u>>v;
g[sto[v]].push_back(sto[u]);
}
for (int i=1;i<=cnt;i++) {
if (!dfn[i]) tarjan(i);
}
for (pair<int,int> p:mr) {
if (vis[p.first]==vis[p.second]) cout<<"Unsafe\n";
else cout<<"Safe\n";
}
return 0;
}
评论（0）
暂无评论