Pagini recente » Cod sursa (job #2690967) | Cod sursa (job #1069259) | Cod sursa (job #2361134) | Cod sursa (job #32646) | Cod sursa (job #2571085)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define N 100005
int n, m, i, nrc, h[N], low[N], x, inaltime;
bitset<N> viz, eInStiva;
vector<int>L[N]; ///listele de adiacenta
vector<int>c[N]; ///componenetele tare conexe
stack<int>st;
void citireGraf(){
int i, x, y;
fin >> n >> m;
for(i = 1; i <= m; i++){
fin >> x >> y;
L[x].push_back(y);
}
}
void dfs(int x) {
int z;
inaltime++; /// urc in stiva
viz[x] = 1;
low[x] = h[x] = inaltime;
st.push(x);
eInStiva[x] = 1;
for(auto y : L[x]) {
if(viz[y] == 0){
dfs(y);
low[x] = min(low[x], low[y]);///actualizez cel mai jos punct in care pot ajunge din x
}
else if(eInStiva[y])
low[x] = min(low[x], h[y]);
}
///m-am intros intr-un punct sursa -- extrag componenta tare conexa
if (low[x] == h[x]){
nrc++;
do{
z = st.top();
st.pop();
eInStiva[z] = 0;
c[nrc].push_back(z);
}while(z!=x);
}
}
int main() {
citireGraf();
for(i = 1; i <= n; i++)
if(viz[i] == 0)
dfs(i);
///afisez componentele tare conexe
fout<< nrc << '\n';
for(i = 1; i <= nrc; i++){
for (auto x : c[i])
fout << x <<' ';
fout <<'\n';
}
fin.close(); fout.close();
return 0;
}