//DFS tree
int h[maxn],in[maxn],out[maxn],low[maxn];
void DFS(int u, int v)
{
++ti;
in[u]=ti;
low[u]=ti;
for(int i:adj[u])
{
if(i==v) continue;
if(!in[i])
{
DFS(i,u);
low[u]=min(low[u],low[i]);
}
else low[u]=min(low[u],in[i]);
}
out[u]=ti;
}
in and out arrays will be calculated as in a normal Euler tour. The rest will be an array that helps us identify whether a vertex is a joint or an edge is a bridge.
Explanation: A bridge is an edge that, when removed it, increases the number of connected components in the graph.
→ Therefore, to check if an edge (u,v) is a bridge, simply check if low(u) = in(u). If so, it is a bridge edge.
Explanation: A joint is a vertex that, when removed along with its incident edges, increases the number of connected components in the graph.
We will divide into 2 cases:
u, where v is a direct child of u in the DFS tree). If there exists a vertex v such that low(v) ≥ num(u), then u is a joint. → With this checking method, we can determine whether a vertex is a joint directly during the DFS process.
bool mark [maxn];
// mark[u] = true means that u is a joint
void DFS(int u, int v)
{
int cnt=0;
++ti;
in[u]=low[u]=ti;
for(int i:adj[u])
{
if(i==v) continue;
if(!in[i])
{
++cnt;
DFS(i,u);
low[u]=min(low[u],low[i]);
if(v==0 && cnt>1) mark[u]=true;
else if(low[i]>=in[u]) mark[u]=true;
}
else low[u]=min(low[u],in[i]);
}
out[u]=ti;
}
//SCC - Tarjan's algorithm
void DFS(int u)
{
in[u] = low[u] = ++ti;
f.push(u);
for(int i:adj[u])
{
if(deleted[i]) continue;
if(in[i]) low[u] = min(low[u],in[i]);
else
{
DFS(i);
low[u] = min(low[u],low[i]);
}
}
if(low[u] == in[u])
{
scc++;
int v;
do {
v = f.top();
f.pop();
id[v] = scc;
deleted[v] = true;
}
while (v != u);
}
}
void input()
{
cin>>n>>m;
for(int i=1,u,v;i<=m;++i)
{
cin>>u>>v;
adj[u].pp(v);
}
for(int i=1;i<=n;++i)
if(!in[i]) DFS(i);
cout<<scc;
}