Pagini recente » Cod sursa (job #2358034) | Cod sursa (job #1140599) | Cod sursa (job #1972575) | Cod sursa (job #1947869) | Cod sursa (job #3204047)
#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, time;
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 = ++time;
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(){
time = 0;
for(int i = 1; i <= n; i++){
if(!nodes[i].timp_introdus){
dfs(i);
}
}
}
void afisare_componente(){
fout << componente.size() << '\n';
for(vector<int> ctc : componente){
for(int element : ctc){
fout << element << " ";
}
fout << '\n';
}
}
int main(){
citire();
dfs_starter();
afisare_componente();
return 0;
}