Pagini recente » Cod sursa (job #238148) | Cod sursa (job #2738453) | Cod sursa (job #2264447) | Cod sursa (job #2549912) | Cod sursa (job #2324651)
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m , nrcc;
vector <int> T[nmax];
vector <int> L[nmax];
vector <int> sol[nmax];
bitset <nmax> viz;
stack <int> st;
void Read()
{
int x, y;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> x >> y;
L[x].push_back(y);
T[y].push_back(x);
}
}
void DFS1(int k)
{
viz[k] = 1;
for(auto i : L[k])
if(viz[i] == 0)
DFS1(i);
st.push(k);
}
void DFS2(int k)
{
viz[k] = 1;
sol[nrcc].push_back(k);
for(auto i : T[k])
if(viz[i] == 0)
DFS2(i);
}
void Print()
{
fout << nrcc << "\n";
for(int i = 1;i <= nrcc; i++)
{
for(auto j : sol[i])
fout << j << " ";
fout << "\n";
}
}
void Do()
{
int cNode;
for(int i = 1; i <= n; i++)
if(viz[i] == 0)
DFS1(i);
viz.reset();
while(!st.empty())
{
cNode = st.top();
st.pop();
if(viz[cNode] == 0)
{
nrcc++;
DFS2(cNode);
}
}
Print();
}
int main()
{
Read();
Do();
return 0;
}