Pagini recente » Cod sursa (job #583573) | Cod sursa (job #369268) | Cod sursa (job #1876367) | Cod sursa (job #2436088) | Cod sursa (job #3030282)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, id ,ctc, root[100001], viz[100001], in_st[100001];
vector <int> graf[100001];
vector <int> CTC[100001];
stack <int> st;
void citire() {
int x, y;
fin >> n >> m;
for (int i = 1 ; i <= m ; i++) {
fin >> x >> y;
graf[x].push_back(y);
}
}
void dfs(int nod){
int aux;
st.push(nod);
in_st[nod]=1;
id++;
viz[nod]=id;
root[nod]=id;
for (int el: graf[nod]) {
if (viz[el]==0) dfs(el);
if (in_st[el]) root[nod]=min(root[nod],root[el]);
}
if (viz[nod]==root[nod]) {
while (!st.empty()) {
aux=st.top();
CTC[ctc].push_back(aux);
st.pop();
in_st[aux]=0;
root[aux]=viz[aux];
if (aux==nod) break;
}
ctc++;
}
}
int main(){
citire();
for (int i=1;i<=n;i++){
if (viz[i]==0) dfs(i);
}
fout << ctc;
for (int i=0;i<=ctc;i++) {
fout << "\n";
for (int j:CTC[i]) {
fout << j << " ";
}
}
}