PROBLEM LINK:
Author- Samarth Mittal
Editorialist- Samarth Mittal
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
PROBLEM:
Given a graph with N trees, M pavements and X animals. Find the number of harmful animals. Animals are harmful if they stand on a path which is the only path connecting its end-points. (i.e. is an edge of a graph whose deletion increases its number of connected components.)
QUICK EXPLANATION:
One needs to find all the special paths (bridges in the given graph and calculate the number of animals sitting on these paths.
EXPLANATION:
Let all the N trees and M pavements in the problem be treated as N nodes and M paths in an undirected graph.
A path is special if it is the only possible path to connect its end-points, thus a bridge. A bridge is defined as an edge which, when removed, makes the graph disconnected.
The problem then simplifies to finding all the bridges in the graph and calculating the number of animals which sit on those bridges.
This problem can be divided into two tasks -
1) Find the bridges in the given graph.
2) Finding the number of animals which are sitting on these bridges.
To find the bridges, pick an arbitrary vertex of the graph, not visited yet and run a depth first search from it.
For a vertex v, the current edge (v, to) is a bridge if and only if none of the vertices to and its descendants in the DFS traversal has a back-edge to vertex v or any of its ancestors.
Reference.
Resources for learning.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ff first
#define ss second
#define pb(x) push_back(x)
#define testcase(t) int t;cin>>t;while(t--)
#define mp(x,y) make_pair(x,y)
#define in(x) insert(x)
#define rep(i,a,b) for (__typeof((b)) i=(a);i<=(b);i++)
#define nrep(i,a,b) for (__typeof((b)) i=(b);i>=(a);i--)
#define PI 3.14159265358979323846
#define SP(x) setprecision(x)
#define reflex ios_base::sync_with_stdio(false);cin.tie(NULL)
#define M 1000000007
#define SIZE 100005
#define pii pair<int, int>
#define mem(arr,val) memset(arr,val,sizeof(arr)) //For "0" and "-1"
int vis[SIZE],disc[SIZE],low[SIZE],br_check[SIZE];
vector<pii> v[SIZE];
int tim = 0;
void dfs(int x, int par)
{
vis[x] = 1;
tim++;
disc[x] = low[x] = tim;
for(auto it: v[x])
{
int child = it.ff, ind = it.ss;
if(child == par) continue;
if(vis[child] == 0)
{
dfs(child, x);
low[x] = min(low[x], low[child]);
if(low[child] > disc[x]) br_check[ind]=1;
}
else low[x] = min(low[x], disc[child]);
}
}
int main(){
int q,n,m,a,b;
cin>>n>>m;
assert(1<=n && n<=1e5);
assert(1<=m && m<=1e5);
rep(i,1,m)
{
cin>>a>>b;
v[a].pb(mp(b,i));
v[b].pb(mp(a,i));
}
mem(vis, 0);
mem(br_check, 0);
rep(i,1,n)
{
if(vis[i]==0) dfs(i,-1);
}
cin>>q;
assert(1<=q && q<=m);
int ans=0;
while(q--)
{
int val;
cin>>val;
assert(1<=val && val<=min(100000, (n*(n-1))/2));
if(br_check[val]==1) ans++;
}
cout<<ans<<endl;
}