Pagini recente » Cod sursa (job #1092498) | Cod sursa (job #994565) | Cod sursa (job #2553208) | Cod sursa (job #1429204) | Cod sursa (job #1836245)
#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 st[VAL], top;
int loc[VAL], K;
bool viz[VAL];
vector<int> v[VAL];
vector<int> G[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;
void visit(int i)
{
vector<int> :: iterator it;
if (viz[i]==false)
{
viz[i]=true;
for (it=v[i].begin(); it!=v[i].end(); it++)
visit(*it);
st[++top]=i;
}
}
void ataseaza(int i, int root)
{
vector<int> :: iterator it;
if (loc[i]==0)
{
loc[i]=root;
comp[root].push_back(i);
for (it=G[i].begin(); it!=G[i].end(); it++)
ataseaza(*it, root);
}
}
int main()
{
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> a >> b;
v[a].push_back(b);
G[b].push_back(a);
}
for (i=1; i<=N; i++)
visit(i);
while (top!=0)
{
ataseaza(st[top], st[top]);
top--;
}
for (i=1; i<=N; i++)
if (comp[i].size()!=0)
K++;
fout << K << '\n';
for (i=1; i<=N; i++)
{
if (comp[i].size()>0)
{
for (it=comp[i].begin(); it!=comp[i].end(); it++)
fout << *it << " ";
fout << '\n';
}
}
fin.close();
fout.close();
return 0;
}