Pagini recente » Cod sursa (job #2411649) | Cod sursa (job #2652707) | Cod sursa (job #2941343) | Borderou de evaluare (job #1796797) | Cod sursa (job #3273088)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax = 100005;
struct nod{
int timp_vizitat, timp_atins;
vector<int> vecini;
};
int n, m, timp, nr_componenta;
nod graf[Nmax];
stack<int> st;
vector<int> componente[Nmax];
void citire_arbore(){
int nod1, nod2;
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> nod1 >> nod2;
graf[nod1].vecini.push_back(nod2);
}
}
void dfs(int nod){
graf[nod].timp_vizitat = ++timp;
graf[nod].timp_atins = timp;
st.push(nod);
for(int vecin : graf[nod].vecini){
if(!graf[vecin].timp_vizitat){
dfs(vecin);
}
graf[nod].timp_atins = min(graf[nod].timp_atins, graf[vecin].timp_atins);
}
if(graf[nod].timp_atins == graf[nod].timp_vizitat){
nr_componenta++;
while(!st.empty() && st.top() != nod){
componente[nr_componenta].push_back(st.top());
st.pop();
}
componente[nr_componenta].push_back(nod);
st.pop();
}
}
void tarjan(){
nr_componenta = timp = 0;
for(int i = 1; i <= n; i++){
if(!graf[i].timp_vizitat){
dfs(i);
}
}
}
void afisare(){
fout << nr_componenta << '\n';
for(int i = 1; i <= nr_componenta; i++){
for(int element : componente[i]){
fout << element << ' ';
}
fout << '\n';
}
}
int main(){
citire_arbore();
tarjan();
afisare();
return 0;
}