随手粘一个以前oi时期的博文看看效果
今天考试T1考这个，以前只在床上看书时推过一遍，现在忘完了。 复习（重学）一下。
学习博客：
OIWIKI
DFS 树
树枝边：DFS时经过的边，即DFS搜索树上的边。
前向边：与DFS方向一致，从某个结点指向其某个子孙的边。
后向边：与DFS方向相反，从某个结点指向其某个祖先的边。（返祖边）
横叉边：从某个结点指向搜索树中的另一子树中的某结点的边。
强联通分量
直接写过程，证明抽象式理解即可（busi）。
DFS的时候：
-
\(v\) 未被访问，常规操作加更新 \(low\) ，同时入栈。
-
\(v\) 被访问过了，用它来回溯更新 \(low\) 。
回溯的时候：
如果 \(dfn[x]==low[x]\) ，就弹出它及以上的为一个 \(SCC\)
抽象式证明：
当它能回到以前的时候，因为 \(low\) 被更新了，所以不会出栈。如果是单个 \(SCC\) 的话，那么就先出栈了，就无需考虑了。
例题（以前做过的就不写了）：
唯一要关注的是建图的关系 （可怕），写在代码里了。
#include<bits/stdc++.h>
using namespace std;
const int MX=4*10000+10;
#define LL long long
#define inf 0x3f3f3f3f
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m;
unordered_map<string,int> mp;
int mp_idx=0;
inline int _hash(string s)
{
if(!mp[s])
{
mp[s]=++mp_idx;
return mp_idx;
}
else return mp[s];
}
struct tEdge
{
int to;
int next;
}edge[MX<<2];
int head[MX],cnt=0;
inline void add(int from,int to)
{
edge[++cnt].to=to,edge[cnt].next=head[from];
head[from]=cnt;
}
int dfn[MX],low[MX];
int idx=0;
int scc[MX],scc_idx=0;
bool in_stack[MX];
std::vector<int> stk;
inline void dfs(int now)
{
//printf("now: %d\n",now);
dfn[now]=low[now]=++idx;
in_stack[now]=1;
stk.push_back(now);
for(int i=head[now];i;i=edge[i].next)
{
int yt=edge[i].to;
if(!dfn[yt])
{
dfs(yt);
low[now]=min(low[now],low[yt]);
}
else if(in_stack[yt])//只有还在栈的（没有处理的）才更新，不然没用
{
low[now]=min(low[now],dfn[yt]);
}
}
if(dfn[now]==low[now])
{
scc_idx++;
int y;
do
{
y=stk.back();
scc[y]=scc_idx;
in_stack[y]=0;
stk.pop_back();
}while(y!=now);
}
}
string fq[MX][2];
int main(int argc, char const *argv[])
{
n=read();
for(int i=1;i<=n;i++)
{
cin>>fq[i][0]>>fq[i][1];
int x1=_hash(fq[i][0]),x2=_hash(fq[i][1]);
add(x2,x1);
}
m=read();
for(int i=1;i<=m;i++)
{
string s1,s2;
cin>>s1>>s2;
int x1=_hash(s1),x2=_hash(s2);
add(x1,x2);
}
for(int i=1;i<=n*2;i++)
{
if(!dfn[i]) dfs(i);
}
//printf("%d\n",scc_idx);
for(int i=1;i<=n;i++)//女的抛了个男的，男的找个新的女的，新的女的抛了她的男的，那个男的找了一开始那个女的......\jk
{
int x1=_hash(fq[i][0]),x2=_hash(fq[i][1]);
if(scc[x1]==scc[x2])
{
printf("Unsafe\n");
}
else
{
printf("Safe\n");
}
}
return 0;
}
直接跑 \(tarjan\) 即可，存下每个 \(scc\) 的元素，排序+乘法原理。
#include<bits/stdc++.h>
using namespace std;
const int N=1*100000+233;
const int M=3*100000+233;
#define LL long long
#define inf 0x3f3f3f3f
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m;
int w[N];
struct tEdge
{
int to,next;
}edge[M];
int head[N],cnt=0;
inline void add(int from,int to)
{
edge[++cnt].to=to,edge[cnt].next=head[from];
head[from]=cnt;
}
int dfn[N],low[N],idx=0;
bool in_stack[N];
std::vector<int> stk;
int scc[N],scc_idx=0;
std::vector<int> bk[N];
inline void tarjan(int now)
{
dfn[now]=low[now]=++idx;
stk.push_back(now);
in_stack[now]=1;
for(int i=head[now];i;i=edge[i].next)
{
int yt=edge[i].to;
if(!dfn[yt])
{
tarjan(yt);
low[now]=min(low[now],low[yt]);
}
else if(in_stack[yt])
{
low[now]=min(low[now],dfn[yt]);
}
}
if(dfn[now]==low[now])
{
int y;
++scc_idx;
do
{
y=stk.back();
stk.pop_back();
in_stack[y]=0;
scc[y]=scc_idx;
bk[scc_idx].push_back(w[y]);
}
while(y!=now);
}
}
int main(int argc, char const *argv[])
{
n=read();
for(int i=1;i<=n;i++) w[i]=read();
m=read();
for(int i=1;i<=m;i++)
{
int u,v;
u=read(),v=read();
add(u,v);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i]) tarjan(i);
}
int ans=0;
LL fn=1ll;
for(int i=1;i<=scc_idx;i++)
{
sort(bk[i].begin(),bk[i].end());
int minn=bk[i][0],num=0;
ans+=minn;
for(std::vector<int>::iterator it=bk[i].begin();it!=bk[i].end();it++)
{
if((*it)==minn)
{
num++;
}
else break;
}
fn=fn*(LL)num;
}
cout<<ans<<" "<<fn<<endl;
return 0;
}
强连通分量 END
标签：尝试,ch,idx,int,博客,low,now,yt,美化 From： https://www.cnblogs.com/hewo/p/17626332.html