Pagini recente » Istoria paginii runda/eusebiuoji2004cls9/clasament | Cod sursa (job #988221) | Cod sursa (job #2399198) | Cod sursa (job #332577) | Cod sursa (job #1836228)
#include <fstream>
#include <vector>
#define VAL 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, a, b, i, j;
int sir[VAL], x[VAL];
int poz[VAL], K;
vector<int> v[VAL];
vector<int> G[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;
void dfs(int nr)
{
vector<int> :: iterator it;
x[nr]=K;
comp[K].push_back(nr);
for (it=G[nr].begin(); it!=G[nr].end(); it++)
if (x[*it]<1 && poz[*it]>poz[sir[i]])
dfs(*it);
}
int main()
{
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> a >> b;
v[a].push_back(b);
G[b].push_back(a);
x[b]++;
}
for (i=1; i<=N; i++)
{
if (x[i]==0)
{
sir[++K]=i;
poz[i]=K;
}
}
for (i=1; i<=N; i++)
{
for (it=v[i].begin(); it!=v[i].end(); it++)
{
x[*it]--;
if (x[*it]==0)
{
sir[++K]=*it;
poz[*it]=K;
}
}
}
K=0;
for (i=1; i<=N; i++)
{
if (x[sir[i]]<1)
{
++K;
dfs(sir[i]);
}
}
fout << K << '\n';
for (i=1; i<=K; i++)
{
for (it=comp[i].begin(); it!=comp[i].end(); it++)
fout << *it << " ";
fout << '\n';
}
fin.close();
fout.close();
return 0;
}