Pagini recente » Cod sursa (job #305846) | Cod sursa (job #3318529) | Cod sursa (job #3352079) | Cod sursa (job #2474680) | Cod sursa (job #3343976)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m, vizitat[100001], nrc;
vector <int> vecini[100001], transpusa[100001];
stack <int> st;
set <int> rez[100001];
void DFS(int nod) {
vizitat[nod]= 1;
for (auto next : vecini[nod])
if (!vizitat[next])
DFS(next);
st.push(nod);
}
void DFS_T(int nod) {
vizitat[nod]= 2;
rez[nrc].insert(nod);
for (auto next : transpusa[nod])
if (vizitat[next]==1)
DFS_T(next);
}
int main() {
cin>>n>>m;
while (m--)
{
int i, j;
cin>>i>>j;
vecini[i].push_back(j);
transpusa[j].push_back(i);
}
for (int i=1; i<=n; i++)
if (!vizitat[i])
DFS(i);
while (!st.empty())
{
int nod= st.top();
st.pop();
if (vizitat[nod]==1)
{
nrc++;
DFS_T(nod);
}
}
cout<< nrc <<"\n";
for (int i=1; i<=nrc; i++, cout<<"\n")
for (auto x : rez[i])
cout<< x <<" ";
return 0;
}