Pagini recente » Cod sursa (job #1404778) | Cod sursa (job #1250811) | Cod sursa (job #1599989) | Cod sursa (job #943111) | Cod sursa (job #1834327)
#include <fstream>
#include <vector>
#include <cstring>
#define VAL 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, i, j;
int x, y, K;
int gasit[VAL];
bool ok[VAL], ok2[VAL];
vector<int> G[VAL];
vector<int> Ginv[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;
void dfs(int x, vector<int> Graf[], bool gas[])
{
vector<int> :: iterator it;
gas[x]=true;
for (it=Graf[x].begin(); it!=Graf[x].end(); it++)
if (gas[*it]==false)
dfs(*it, Graf, gas);
}
int main()
{
fin >> N >> M;
for (i=1; i<=M; i++)
{
fin >> x >> y;
G[x].push_back(y);
Ginv[y].push_back(x);
}
for (i=1; i<=N; i++)
{
if (gasit[i]==0)
{
++K;
gasit[i]=K;
comp[K].push_back(i);
ok[i]=true;
dfs(i, G, ok);
ok2[i]=true;
dfs(i, Ginv, ok2);
for (j=1; j<=N; j++)
if (ok[j]==true && ok2[j]==true)
gasit[j]=K;
memset(ok, false, sizeof(ok));
memset(ok2, false, sizeof(ok2));
}
else
comp[gasit[i]].push_back(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;
}