Pagini recente » Cod sursa (job #1939956) | Cod sursa (job #336213) | Cod sursa (job #3270982) | Cod sursa (job #2625182) | Cod sursa (job #3204050)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax = 100005;
struct nod{
vector<int> vecini;
int timp_introdus, low;
bool inStiva;
};
int n, m, timp;
nod nodes[Nmax];
stack<int> st;
vector<int> ctc;
vector<vector<int>> componente;
void citire(){
ifstream fin("ctc.in");
int start, finish;
fin >> n >> m;
for(int i = 1; i <= m; i++){
fin >> start >> finish;
nodes[start].vecini.push_back(finish);
}
}
void elimina_din_stiva(){
nodes[st.top()].inStiva = 0;
ctc.push_back(st.top());
st.pop();
}
void marcare_componenta(int root){
ctc.clear();
while(st.top() != root){
elimina_din_stiva();
}
elimina_din_stiva();
componente.push_back(ctc);
}
void dfs(int nod){
nodes[nod].timp_introdus = nodes[nod].low = ++timp;
nodes[nod].inStiva = 1;
st.push(nod);
for(int vecin : nodes[nod].vecini){
if(!nodes[vecin].timp_introdus){
dfs(vecin);
nodes[nod].low = min(nodes[nod].low, nodes[vecin].low);
}
else if(nodes[vecin].inStiva){
nodes[nod].low = min(nodes[nod].low, nodes[vecin].low);
}
}
if(nodes[nod].timp_introdus == nodes[nod].low){
marcare_componenta(nod);
}
}
void dfs_starter(){
timp = 0;
for(int i = 1; i <= n; i++){
if(!nodes[i].timp_introdus){
dfs(i);
}
}
}
void afisare_componente(){
fout << componente.size() << '\n';
for(int i = componente.size() - 1; i >= 0; i--){
ctc = componente[i];
for(int j = ctc.size() - 1; j >= 0; j--){
fout << ctc[j] << " ";
}
fout << '\n';
}
}
int main(){
citire();
dfs_starter();
afisare_componente();
return 0;
}