Pagini recente » Cod sursa (job #1437974) | Cod sursa (job #1933004) | Cod sursa (job #24369) | Cod sursa (job #3285641) | Cod sursa (job #2528255)
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, j, low[100002], niv[100002], componente, index = 1, x, y;
bitset<100002> in_stiva;
vector<int> v[100002], sol[100002];
stack<int> stiva;
void dfs(int nod){
niv[nod] = index++;
stiva.push(nod);
in_stiva[nod] = 1;
low[nod] = niv[nod]; /// definit ca nivelul cel mai mic al unui nod aflata deja in stiva la care se poate ajunge din nod PRIN SUBGRAFUL SAU
for(int i = 0;i<v[nod].size();i++){
int vecin = v[nod][i];
if(niv[vecin] == 0){ /// daca nu a fost deja pus in coada
dfs(vecin);
low[nod] = min(low[nod], low[vecin]);
}
else
if(in_stiva[vecin]) /// daca nu mai e in stiva, inseamna ca deja a fost pus intr-o componenta conexa si trebuie sa il ignor
low[nod] = min(low[nod], niv[vecin]); /// ma opresc la vecin, nu iau in calcul low-ul lui, deoarece low este definit ca fiind nodul la care ajungi prin subgraful lui nod, or vecin nu se afla in subgraful lui nod, intrucat fusese pus de dinainte in stiva (cred ca, in cazul problemei de fata, oricum nu influenteaza, pentru ca nu modifica nimic la radacina componentei conexe)
}
if(low[nod] == niv[nod]){
componente++;
int crt;
do{
crt = stiva.top();
stiva.pop();
in_stiva[crt] = 0;
sol[componente].push_back(crt);
} while(crt != nod);
}
}
int main(){
fin>>n>>m;
while(m--){
fin>>x>>y;
v[x].push_back(y);
}
for(i=1;i<=n;i++)
if(niv[i] == 0)
dfs(i);
fout<<componente<<"\n";
for(i=1;i<=componente;i++){
for(j=0;j<sol[i].size();j++)
fout<<sol[i][j]<<" ";
fout<<"\n";
}
return 0;
}