Dsa
Union Find
Medium
Noble Substances
In a chemistry lab, there are N chemical elements (0 to N-1). Some elements are 'Noble'. When elements bond, they form a compound. A compound is 'Stable' if and only if it contains exactly one Noble element. If a compound has zero Noble elements or more than one, it is 'Unstable'. Given the list of Noble elements and a sequence of bonds, report the number of elements that belong to Stable compounds after all bonds are processed.
Input Format:
The first line contains N (elements), M (bonds), and P (number of Noble elements).
The second line contains P unique integers representing the IDs of Noble elements.
The next M lines each contain two integers u and v, representing a bond between element u and element v.
Output Format:
Print a single integer: the total number of elements that are part of a Stable compound after all M bonds.
Example:
Input:
4 2 2
0 3
0 1
1 2
Output:
3
Explanation:
Noble elements are {0, 3}. Bonds: (0,1), (1,2).
Compounds: {0,1,2} and {3}.
{0,1,2} has one Noble (0) -> Stable.
{3} has one Noble (3) -> Stable.
Total elements in stable compounds: 3 + 1 = 4. Wait, the example output is 4.
Key concepts
union_findattribute_tracking
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now