Pagini recente » Cod sursa (job #3227349) | Cod sursa (job #648571) | Cod sursa (job #2926118) | Cod sursa (job #1523499) | Cod sursa (job #2665775)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
int n, m, i, j, k, index, ord[100005], niv_min[100005];
vector<int> vec[100005], comp[100005];
stack<int> st;
set<int> s;
void tarjan(int nod) {
int ind, x;
ord[nod] = index; /// ordinea de vizitare
niv_min[nod] = index; /// nivelul radacinei componentei conexe in care se afla nodul curent; initial, conideram nodul ca radacina
index++;
st.push(nod);
s.insert(nod);
for(ind = 0; ind < vec[nod].size(); ind++)
if(!ord[vec[nod][ind]]) { /// pentru vecinii nevizitati
tarjan(vec[nod][ind]); /// aplic tarjan()
niv_min[nod] = min(niv_min[nod], niv_min[vec[nod][ind]]); /// actualizez nivelul radacinii lui nod
}
else if(s.find(vec[nod][ind]) != s.end()) /// daca vecinul este in stiva
niv_min[nod] = min(niv_min[nod], ord[vec[nod][ind]]); /// actualizez nivelul radacinii
if(ord[nod] == niv_min[nod]) /// nod este radacina daca ord[nod] == niv_min[nod]
while(!st.empty()) { /// in componenta conexa intra toate nodurile din stiva, care sunt deasupra lui nod
x = st.top();
st.pop();
s.erase(x);
comp[k].push_back(x);
if(x == nod) {
k++;
break;
}
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
while(m) {
f >> i >> j;
vec[i].push_back(j);
m--;
}
f.close();
k = 0;
index = 1;
for(i = 1; i <= n; i++)
if(!ord[i])
tarjan(i); /// aplic algoritmul lui tarjan pentru nodurile nevizitate
g << k << '\n';
for(i = 0; i < k; i++, g << '\n')
for(j = 0; j < comp[i].size(); j++)
g << comp[i][j] << ' ';
g.close();
return 0;
}