Pagini recente » Monitorul de evaluare | Cod sursa (job #854443) | Cod sursa (job #854162) | Monitorul de evaluare | Cod sursa (job #3337860)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
vector <int> ad[100005];
vector <int> ad_r[100005];
vector <int> c[100005];
stack<int> T;
int viz[100005];
int ctc=0, cnt=0;
void dfs(int nod)
{
viz[nod]=1;
for(auto w : ad[nod])
{
if(!viz[w])
{
dfs(w);
}
}
T.push(nod);
}
void dfst(int nod)
{
viz[nod]=1;
c[cnt].push_back(nod);
for(auto &w : ad_r[nod])
{
if(!viz[w])
{
dfst(w);
}
}
}
int main()
{
int a, b;
fin >> N >> M;
for(int i=1;i<=M;i++)
{
fin >> a >> b;
ad[a].push_back(b);
ad_r[b].push_back(a);
}
for(int i=1;i<=N;i++)
{
if(!viz[i])dfs(i);
}
for(int i=1;i<=N;i++)
{
viz[i]=0;
}
while(!T.empty())
{
int v=T.top();
T.pop();
if(!viz[v])cnt++,dfst(v),ctc++;
}
fout << ctc << '\n';
for(int i=1;i<=cnt;i++)
{
for(auto w: c[i])
{
fout << w << ' ';
}
fout << '\n';
}
return 0;
}