Pagini recente » Cod sursa (job #2348820) | Cod sursa (job #1332135) | Cod sursa (job #1219860) | Cod sursa (job #1687002) | Cod sursa (job #3030907)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m,viz[100005],nr_CTC;
vector<int>L[100005],LT[100005],LTC[100005];
stack<int>st;
void dfs(int x){
viz[x] = 1;
int nr = L[x].size();
for(int i = 0; i < nr; i++){
if(!viz[L[x][i]])
dfs(L[x][i]);
}
st.push(x);
}
void dfs2(int x){
viz[x] = 2;
LTC[nr_CTC].push_back(x);
int nr = LT[x].size();
for(int i = 0; i < nr; i++){
if(viz[LT[x][i]] == 1)
dfs2(LT[x][i]);
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++){
int a,b;
in >> a >> b;
L[a].push_back(b);
LT[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!viz[i])
dfs(i);
while(!st.empty()){
int nod = st.top();
st.pop();
if(viz[nod]==1){
nr_CTC++;
dfs2(nod);
}
}
out << nr_CTC << "\n";
for(int i = 1; i <= nr_CTC; i++,out << "\n")
for(int j = 0; j < LTC[i].size(); j++)
out << LTC[i][j] << " ";
return 0;
}